LeetCode 413. 等差数列划分（DP）

1. 题目

一个数列的等差数列子数组有多少个。

A = [1, 2, 3, 4]

返回: 3, A 中有三个子等差数组: [1, 2, 3], [2, 3, 4] 
		以及自身 [1, 2, 3, 4]。

2. 解题

状态公式 i f ( A [ i ] − A [ i − 1 ] = A [ i − 1 ] − A [ i − 2 ] ) , t h e n d p [ i ] = d p [ i − 1 ] + 1 , i > = 2 if (A[i]-A[i-1] =A[i-1]-A[i-2]) , \quad then \quad dp[i] = dp[i-1]+1, i>=2 if(A[i]−A[i−1]=A[i−1]−A[i−2]),thendp[i]=dp[i−1]+1,i>=2

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& A) {
        if(A.size() <= 2)
        	return 0;
        int dp[A.size()] = {0}, differ = A[1]-A[0], sum = 0;
        for(int i = 2; i < A.size(); ++i)
        {
        	if(A[i]-A[i-1] == differ)
    		{
    			dp[i] = dp[i-1]+1;
    			sum += dp[i];
    		}
        	else
        		differ = A[i]-A[i-1];
        }
        return sum;
    }
};