《算法题讲解指南：动态规划算法--子数组系列》--23.等差数列划分，24.最长湍流子数组

小叶-duck个人主页❄️个人专栏《Data-Structure-Learning》《C入门到进阶自我学习过程记录》《算法题讲解指南》--优选算法《算法题讲解指南》--递归、搜索与回溯算法《算法题讲解指南》--动态规划算法✨未择之路不须回头已择之路纵是荆棘遍野亦作花海遨游目录23.等差数列划分题目链接题目描述题目示例解法(动态规划)算法思路C算法代码算法总结及流程解析24.最长湍流子数组题目链接题目描述题目示例解法(动态规划)算法思路C算法代码算法总结及流程解析结束语23.等差数列划分题目链接413. 等差数列划分 - 力扣LeetCode题目描述题目示例解法(动态规划)算法思路1.状态表示由于我们的研究对象是「一段连续的区间」如果我们状态表示定义成[0i]区间内一共有多少等差数列那么我们在分析dp[i]的状态转移时会无从下手因为我们不清楚前面那么多的「等差数列都在什么位置」。所以说我们定义的状态表示必须让等差数列「有迹可循」让状态转移的时候能找到「大部队」。因此我们可以「固定死等差数列的结尾」定义下面的状态表示dp[i] 表示必须「以i位置的元素为结尾」的等差数列有多少种。2.状态转移方程我们需要了解一下等差数列的性质:如果abc三个数成等差数列这时候来了一个d其中bcd也能构成一个等差数列那么abcd四个数能够成等差序列吗?答案是:显然的。因为他们之间相邻两个元素之间的差值都是一样的。有了这个理解我们就可以转而分析我们的状态转移方程了。对于dp[i]位置的元素nums[i]会与前面的两个元素有下面两种情况i.nums[i-2]nums[i- 1]nums[i]三个元素不能构成等差数列:那么以nums[i]为结尾的等差数列就不存在此时dp[i];ii.nums[i- 2]nums[i- 1]nums[i]三个元素可以构成等差数列:那么以nums[i-1]为结尾的所有等差数列后面填上一个 nums[i]也是一个等差数列此时dp[i]dp[i-1] 。但是因为nums[i-2]nums[i-1]nums[i]三者又能构成一个新的等差数列因此要在之前的基础上再添上一个等差数列于是dp[i] dp[i- 1] 1。综上所述:状态转移方程为当nums[i-2] nums[i] ! 2 * nums[i - 1] 时, dp[i] 0当nums[i -2] nums[i] 2 * nums[i - 1] 时dp[i] 1 dp[i-1]3.初始化由于需要用到前两个位置的元素但是前两个位置的元素又无法构成等差数列因此dp[0] dp[1] 0。4.填表顺序毫无疑问是「从左往右」。5.返回值因为我们要的是所有的等差数列的个数因此需要返回整个 dp表里面的元素之和。C算法代码class Solution { public: int numberOfArithmeticSlices(vectorint nums) { int n nums.size(); if(n 1 || n 2) { return 0; } vectorint dp(n); dp[0] dp[1] 0; 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; } else { dp[i] 0; } } int ret 0; for(int i 0; i n; i) { ret dp[i]; } return ret; } };算法总结及流程解析24.最长湍流子数组题目链接978. 最长湍流子数组 - 力扣LeetCode题目描述题目示例解法(动态规划)算法思路1.状态表示我们先尝试定义状态表示为dp[i]表示「以i位置为结尾的最长湍流数组的长度」。但是问题来了如果状态表示这样定义的话以i位置为结尾的最长湍流数组的长度我们没法从之前的状态推导出来。因为我们不知道前一个最长湍流数组的结尾处是递增的还是递减的。因此我们需要状态表示能表示多一点的信息:要能让我们知道这一个最长湍流数组的结尾是「递增」的还是「递减」的。因此需要两个dp表f[i]表示:以i位置元素为结尾的所有子数组中最后呈现「上升状态」下的最长湍流数组的长度;g[i]表示:以i位置元素为结尾的所有子数组中最后呈现「下降状态」下的最长湍流数组的长度。2.状态转移方程对于i位置的元素arr[i]有下面两种情况i.arr[i]arr[i-1]:如果i位置的元素比i-1位置的元素大说明接下来应该去找i -1 位置结尾并且i-1 位置元素比前一个元素小的序列那就是g[i-1]。更新 f[i]位置的值:f[i]g[i-1] 1;ii.arr[i] arr[i-1]:如果i位置的元素比i-1 位置的元素小说明接下来应该去找i- 1 位置结尾并且i-1 位置元素比前一个元素大的序列那就是f[i-1]。更新 g[i]位置的值:g[i] f[i-1] 1 ;iii.arr[i]arr[i -1]:不构成湍流数组。3.初始化所有的元素「单独」都能构成一个湍流数组因此可以将dp表内所有元素初始化为1。由于用到前面的状态因此我们循环的时候从第二个位置开始即可。4.填表顺序毫无疑问是「从左往右两个表一起填」。5.返回值应该返回「两个dp表里面的最大值」我们可以在填表的时候顺便更新一个最大值。C算法代码class Solution { public: int maxTurbulenceSize(vectorint arr) { int n arr.size(); if(n 1) { return 1; } vectorint dp(n); dp[0] 1; dp[1] arr[0] arr[1] ? 1 : 2; for(int i 2; i n; i) { if(arr[i] arr[i - 1]) { dp[i] arr[i - 1] arr[i - 2] ? dp[i - 1] 1 : 2; } else if(arr[i] arr[i - 1]) { dp[i] arr[i - 1] arr[i - 2] ? dp[i - 1] 1 : 2; } else { dp[i] 1; } } int ret INT_MIN; for(int i 0; i n; i) { ret max(ret, dp[i]); } return ret; } };算法总结及流程解析结束语到此23.等差数列划分24.最长湍流子数组 这两道算法题就讲解完了。等差数列划分问题通过定义dp[i]表示以i结尾的等差子数组数量利用相邻元素差值关系进行状态转移最长湍流子数组问题采用双DP数组分别记录上升和下降状态的最长子数组长度根据元素大小关系进行状态更新。希望大家能有所收获