动态规划怎么学？

学习一个算法没有捷径，更何况是学习动态规划，

跟我一起刷动态规划算法题，一起学会动态规划！

1. 题目解析

题目链接：413. 等差数列划分 - 力扣（LeetCode）

这道题目也不难理解，就是让我们求出在这个数组中，

有多少是等差数列的子数组，返回个数即可。

2. 算法原理

1. 状态表示

dp [ i ] 表示以 i 位置元素为结尾的所有子数组中有多少个等差数列。

2. 状态转移方程

状态转移方程有两种情况：

如果 nums[ i - 2 ]，nums[ i - 1 ]，nums[ i ] 构成等差数列，

那么就会在之前的基础上多一个等差数列，也就是这新构成的，

所以这种情况 dp[ i ] = dp[ i - 1 ] + 1。

如果 nums[ i - 2 ]，nums[ i - 1 ]，nums[ i ] 构不能成等差数列，

那只要加上了 nums[ i ] 就无法构成等差数列了，

所以 dp[ i ] = 0。

所以我们的状态转移方程就是：

dp[ i ] = nums[ i - 2 ] - nums[ i - 1 ] == nums[ i - 1 ] - nums[ i ] ? dp[ i - 1 ] + 1 : 0

3. 初始化

这里就不需要虚拟节点了，直接从 2 开始，把 dp[ 0 ] 和 dp[ 1 ] 的位置初始化成 0 即可。

4. 填表顺序

从左往右。

5. 返回值

返回整个 dp 表中所有元素的和（因为题目要计算所有等差数列的和）

3. 代码编写

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