413. Arithmetic Slices

简单的动归，若i-2, i-1, i等差，则以第i个数结尾的等差数列总数=以i-1个数结尾的等差数列总数+1。需要多加考虑，自己的想法是求出每一段的最长等差数列，然后求和即可，效率不高。

自己的代码

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& A) {
        int i = 1, output = 0, length = 0;
        while (i < A.size()){
            if (i != A.size() - 1 && A[i] - A[i-1] == A[i+1] - A[i]){
                ++length;
            }else{
                while (length != 0){
                    output += length;
                    --length;
                }
                
            }
            ++i;
        }
        return output;
    }
};

DP解法

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& A) {
        int n = A.size();
        if (n < 3) return 0;
        vector<int> dp(n, 0); // dp[i] means the number of arithmetic slices ending with A[i]
        if (A[2]-A[1] == A[1]-A[0]) dp[2] = 1; // if the first three numbers are arithmetic or not
        int result = dp[2];
        for (int i = 3; i < n; ++i) {
            // if A[i-2], A[i-1], A[i] are arithmetic, then the number of arithmetic slices ending with A[i] (dp[i])
            // equals to:
            //      the number of arithmetic slices ending with A[i-1] (dp[i-1], all these arithmetic slices appending A[i] are also arithmetic)
            //      +
            //      A[i-2], A[i-1], A[i] (a brand new arithmetic slice)
            // it is how dp[i] = dp[i-1] + 1 comes
            if (A[i]-A[i-1] == A[i-1]-A[i-2]) 
                dp[i] = dp[i-1] + 1;
            result += dp[i]; // accumulate all valid slices
        }
        return result;
    }
};