【算法|动态规划No.19】leetcode413. 等差数列划分

个人主页：兜里有颗棉花糖
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创
收录于专栏【手撕算法系列专栏】【LeetCode】
🍔本专栏旨在提高自己算法能力的同时，记录一下自己的学习过程，希望对大家有所帮助
🍓希望我们一起努力、成长，共同进步。

1️⃣题目描述

如果一个数列 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该数列为等差数列。

• 例如，[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差数列。
  给你一个整数数组 nums ，返回数组 nums 中所有为等差数组的 子数组 个数。

子数组 是数组中的一个连续序列。

示例1：

输入：nums = [1,2,3,4]
输出：3
解释：nums 中有三个子等差数组：[1, 2, 3]、[2, 3, 4] 和 [1,2,3,4] 自身。

示例2：

输入：nums = [1]
输出：0

注意：

• 1 <= nums.length <= 5000
• -1000 <= nums[i] <= 1000

2️⃣题目解析

解题思路如下：

• 整个程序从第三个元素开始遍历序列。对于每一个位置i，首先判断前两个元素nums[i-2]、nums[i-1]和当前元素nums[i]是否构成等差数列。如果构成等差数列，那么dp[i]的值就可以通过dp[i-1] + 1计算得到。其中dp[i-1]表示以前一个元素为结尾的等差数列的个数，而加上当前元素后形成了以当前元素为结尾的新的等差数列。如果不构成等差数列，那么dp[i]的值就设为0，代表不以当前元素为结尾的等差数列个数为0。

3️⃣解题代码

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n);
        if(n <= 2) return 0;
        int ret = 0;
        for(int i = 2;i < n;i++)
        {
            if(nums[i - 1] - nums[i - 2] == nums[i] - nums[i - 1])
                dp[i] = dp[i - 1] + 1;
            else dp[i] = 0;
            ret += dp[i];
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

最后就通过啦！！！