【学会动态规划】等差数列划分（22）-Toy模板网

这篇具有很好参考价值的文章主要介绍了【学会动态规划】等差数列划分（22）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

动态规划怎么学？

1. 题目解析

2. 算法原理

1. 状态表示

2. 状态转移方程

3. 初始化

4. 填表顺序

5. 返回值

3. 代码编写

写在最后：

动态规划怎么学？

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

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

1. 题目解析

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

【学会动态规划】等差数列划分（22）,学会动态规划,动态规划,算法

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

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

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