Leetcode446 等差数列划分

给定一个长度最大 $1000$ 的序列，求其中长度大于等于 $3$ 的等差数列一共有多少个。

这个数据范围自然容易考虑到 $ O \left( n^2 \right) $ 的DP。

首先需要想到的是，答案恰好等于长度大于等于 $2$ 的等差数列个数减去 $ \frac{n \cdot \left( n - 1 \right)}{2} $

设 $ dp[i][j] $ 代表以第 $i$ 位为末尾公差为 $j$ 的等差数列的个数。

则每一个 $dp[i]$ 的所有状态可以 $O \left( n \right) $ 转移得到。

例如对于序列 $[1,1,2,3,4,6]$

枚举到 $3$ 对 $2$ 的转移时，贡献为 $2$ 为末尾，公差为 $1$ 的转移数 $2$ ( $[1,2]$ 和 $[1,2]$ ) $+1$ ( $[2]$ )。所以以 $3$ 结尾公差为 $1$ 共有3种方案。
枚举到 $4$ 对 $2$ 的转移时，贡献为 $1$ ( $[2]$ )。

事实上，由于公差取值范围很大，需要使用离散化的方式存储（例如unordered_map），故总体复杂度 $O\left(n^2 \log n \right)$ 。

1	class Solution {
2	public:
3	int numberOfArithmeticSlices(vector<int>& a) {
4	typedef long long ll;
5	int n=a.size();
6	if (n<=1) return 0;
7	unordered_map<ll,ll> dp[1010];
8	ll ans=0;
9	for (int i=1;i<n;++i){
10	for (int j=0;j<i;++j){
11	ll x=1ll*a[i]-a[j];
12	auto p=dp[j].find(x);
13	if (p!=dp[j].end()){
14	dp[i][x]+=p->second+1;
15	ans+=p->second+1;
16	}
17	else{
18	dp[i][x]++;
19	ans++;
20	}
21	}
22	}
23	return ans-n*(n-1)/2;
24	}
25	};