当前位置：网站首页>LeetCode 413.等差数列划分

LeetCode 413.等差数列划分

2022-08-09 15:45:00 【老乐大魔王】

代码：

    int numberOfArithmeticSlices(vector<int>& nums) {
    
        int n=nums.size();
        if(n<=2)return 0;
        vector<int> dp(n);
        for(int i=2;i<n;++i){
    
            if(nums[i]-nums[i-1]==nums[i-1]-nums[i-2]){
    
                dp[i]=dp[i-1]+1;
            }
        }
        return accumulate(dp.begin(),dp.end(),0);
    }

解题思路：

定义状态：dp[i]表示从nums[0]到nums[i]（并且以nums[i]为结尾，这句话是关键）的区间内所含有的子等差数列个数
状态转移方程：if(dp[i]-dp[i-1]==dp[i-1]-dp[i-2])dp[i]=dp[i-1]+1
这段代码表示如果nums[i]满足区间(nums[0],nums[i-1])的差值，也就表示出现了一个新的等差区间{nums[i-2],nums[i-1],nums[i]}，那么dp[i]的值等于在dp[i-1]的基础上+1，若nums[i]不满足区间(nums[0],nums[i-1])的差值，那么以nums[i]为结尾的等差序列是不存在的，因此此时dp[i]的值=0

LeetCode413

原网站

版权声明
本文为[老乐大魔王]所创，转载请带上原文链接，感谢
https://blog.csdn.net/qq_27277041/article/details/120305127