【动态规划】23子数组系列_等差数列划分_C++

发布时间:2024年01月18日

题目链接:等差数列划分


目录

题目解析:

算法原理

1.状态表示

2.状态转移方程

3.初始化

4.填表顺序

5.返回值

编写代码


题目解析:

题目让我们求数组?nums?中所有为等差数组的?子数组?个数。

由题可得:

一个等差数列?至少有三个元素;


算法原理:

1.状态表示

先创建一个dp表

首先先思考dp表里面的值所表示的含义(是什么?)

dp[i]表示以i位置为结尾,数组?nums?中所有为等差数组的?子数组?个数

这种状态表示怎么来的?

1.经验+题目要求

用之前或者之后的状态,推导出dp[i][j]的值;

根据最近的最近的一步,来划分问题

经验:以i位置为结尾

题目让我们求数组?nums?中所有为等差数组的?子数组?个数

2.状态转移方程

dp[i]等于什么?

为了满足等差数列,那么[i]-[i-1]==[i-1]-[i-2],

如果满足等差数列,那么i位置等差数组的?子数组?个数应该为i-1位置的等差数组的?子数组?个数再加上1;

而“i-1位置的等差数组的?子数组?个数”正好是我们的状态表示:dp[i-1];

所以此时dp[i]=dp[i-1]+1;

如果不满足等差数列,则i位置等差数组的?子数组?个数应该为0;

所以此时dp[i]=0;

3.初始化

(保证填表的时候不越界)

我们这里需要用到[i-1]、[i-2];

所以需要初始化dp[0]、dp[1];

由于等差数列至少需要3个数,所以dp[0]=dp[1]=0;

4.填表顺序

(为了填写当前状态的时候,所需要的状态已经计算过了)

这里所需要的状态是:dp[i-1]

所以填表顺序:从左往右

5.返回值

(根据题目要求和状态表示)

综上分析:需要返回等差数组的?子数组?个数的总和

返回值为:应为每个位置的累加


编写代码:

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) 
    {
        int n=nums.size();
        vector<int> dp(n);

        if(n==1||n==2)
            return 0;

        dp[0]=0;
        dp[1]=0;
        int ret=0;
        for(int i=2;i<n;i++)
        {
            dp[i]=nums[i]-nums[i-1]==nums[i-1]-nums[i-2]?dp[i-1]+1:0;
            ret+=dp[i];
        }
        return ret;
    }
};

文章来源:https://blog.csdn.net/lsj1345714539566/article/details/135578195
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。