动态规划-子数组系列——413.等差数列划分

1.题目解析

测试用例：413.等差数列划分——力扣

测试用例

2.算法原理

1.状态表示

dp[i]:以第i个位置为结尾的子数组中等差数列的个数

2.状态转移方程

当遇到新的数可以与原来的等差数列构成等差数列说明此时多了一种等差数列的情况则dp[i]=dp[i-1]+1;反之不能构成等差数列的话则一定与前面的子数组无法构成等差数列，此时将dp[i]置为0

3. 初始化

因为等差数列至少三个数，因此要初始化dp表前两个数字，而前两个数一定不能构成等差数列，全部为0即可

4.填表顺序

从左到右

5.返回值

返回整个dp表所以元素的和

3.实战代码

class Solution {
public:int numberOfArithmeticSlices(vector<int>& nums) {int n = nums.size();vector<int> dp(n);int ret = 0;for(int i = 2;i < n;i++){int a = nums[i-2];int b = nums[i-1];int c = nums[i];dp[i] = b-a == c-b ? dp[i-1]+1 : 0;ret += dp[i];}    return ret;}
};