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

1. 题目

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

代码语言：javascript复制

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

代码语言：javascript复制

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;
    }
};

dp 数组

0 人点赞