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

动态规划怎么学？

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

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

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

写在最后：

以上就是本篇文章的内容了，感谢你的阅读。

如果感到有所收获的话可以给博主点一个赞哦。

如果文章内容有遗漏或者错误的地方欢迎私信博主或者在评论区指出~