本文主要是介绍「动态规划」如何求子数组中等差数列的个数?,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
413. 等差数列划分https://leetcode.cn/problems/arithmetic-slices/description/
如果一个数列至少有三个元素,并且任意两个相邻元素之差相同,则称该数列为等差数列。例如,[1,3,5,7,9]、[7,7,7,7]和[3,-1,-5,-9]都是等差数列。给你一个整数数组nums,返回数组nums中所有为等差数组的子数组个数。子数组是数组中的一个连续序列。
- 输入:nums = [1,2,3,4],输出:3,解释:nums中有三个子等差数组:[1, 2, 3]、[2, 3, 4]和[1,2,3,4]自身。
- 输入:nums = [1],输出:0。
提示:1 <= nums.length <= 5000,-1000 <= nums[i] <= 1000。
我们用动态规划的思想来解决这个问题。
确定状态表示:根据经验和题目要求,我们用dp[i]表示:以i位置为结尾的所有子数组中,等差数列的个数。
推导状态转移方程:既然是以i位置为结尾的等差数列,那么nums[i - 2]、nums[i - 1]和nums[i]首先要构成等差数列,因为题目中说明了等差数量的长度至少是3。所以我们可以分类讨论:
- 如果nums[i - 2]、nums[i - 1]和nums[i]不构成等差数列,显然dp[i] = 0。
- 如果nums[i - 2]、nums[i - 1]和nums[i]构成等差数列,那么如果一个等差数列以i - 1位置为结尾,这个等差数列的末尾加上nums[i]就依然是一个等差数列。所以,以i位置为结尾的等差数列分为2类:以i - 1位置为结尾的等差数列的末尾加上nums[i]构成的等差数列,以及nums[i - 2]、nums[i - 1]和nums[i]构成的等差数列。注意:后一种情况不属于前一种情况,因为nums[i - 2]、nums[i - 1]只有2个元素,不构成等差数列。所以,此时dp[i] = dp[i - 1] + 1。
如果nums[i - 2]、nums[i - 1]和nums[i]构成等差数列,那么nums[i - 1] * 2 = nums[i] + nums[i - 2]。所以状态转移方程是:dp[i] = nums[i - 1] * 2 == nums[i] + nums[i - 2] ? dp[i - 1] + 1 : 0。
初始化:根据状态转移方程,我们需要初始化dp[0]和dp[1]的值,防止越界。注意计算dp[1]也会导致越界,因为要判断nums[-1]、nums[0]和nums[1]是否构成等差数列。显然dp[0] = dp[1] = 0,因为等差数列至少有3个元素。
填表顺序:根据状态转移方程,显然要从左往右填表。
返回值:根据状态表示,由于我们不确定等差数列的结尾位置,所以应返回dp表中所有元素的和。
细节问题:dp表的规模和nums相同,均为1 x n。
时间复杂度:O(N),空间复杂度:O(N)。
class Solution {
public:int numberOfArithmeticSlices(vector<int>& nums) {int n = nums.size();// 创建dp表vector<int> dp(n);// 填表for (int i = 2; i < n; i++) {if (nums[i - 1] * 2 == nums[i] + nums[i - 2]) {dp[i] = dp[i - 1] + 1;}}// 返回结果return accumulate(dp.begin(), dp.end(), 0);}
};
这篇关于「动态规划」如何求子数组中等差数列的个数?的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!