LeetCode 446 Arithmetic Slices II - Subsequence

动态规划，求有多少子序列是等差数列

dp[i][diff]表示以第i位数为结尾的且相邻两个数差diff的数列个数（不是等差数列，因为长度为2也会被计算），由于diff的数量范围很大但是很稀疏，所以每一个dp[i]里都是一个哈希表。

其中+1表示前面的数列加上i位的数后的数列，前面表示把前面的数列都往后移一位，去掉第一个数，加上i为最后一个数。

结果的计算就是在dp的过程中把所有的dp[j][diff]累加起来，以为确定了右端点为i时左端点有dp[j][diff]种取法。同时也能保证数列的第三个数才开始算。

C++ Code

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& A) {
        int sz = A.size();
        if(sz <= 2) {
            return 0;
        }
        int cnt = 0;
        vector<unordered_map<long long, int>> dp(sz);
        for(int i = 1; i < sz; ++i) {
            for(int j = 0; j < i; ++j) {
                long long diff = (long long) A[i] - (long long)A[j];
                dp[i][diff] += (dp[j][diff] + 1);
                cnt += dp[j][diff];
            }
        }
        return cnt;
    } 
};