《算法题讲解指南：动态规划算法--子序列问题》--27.最长递增子序列，28.摆动序列

小叶-duck个人主页❄️个人专栏《Data-Structure-Learning》《C入门到进阶自我学习过程记录》《算法题讲解指南》--优选算法《算法题讲解指南》--递归、搜索与回溯算法《算法题讲解指南》--动态规划算法✨未择之路不须回头已择之路纵是荆棘遍野亦作花海遨游目录27.最长递增子序列题目链接题目描述题目示例解法(动态规划)算法思路C算法代码算法总结及流程解析28.摆动序列题目链接题目描述题目示例解法(动态规划):算法思路:C算法代码算法总结及流程解析结束语27.最长递增子序列题目链接300. 最长递增子序列 - 力扣LeetCode题目描述题目示例解法(动态规划)算法思路1.状态表示对于线性dp我们可以用「经验 题目要求」来定义状态表示i.以某个位置为结尾巴拉巴拉;ii.以某个位置为起点巴拉巴拉。这里我们选择比较常用的方式以某个位置为结尾结合题目要求定义一个状态表示dp[i]表示以i位置元素为结尾的「所有子序列」中最长递增子序列的长度。2.状态转移方程对于dp[i]我们可以根据「子序列的构成方式」进行分类讨论i.子序列长度为1:只能自己玩了此时dp[i]1 ;ii.子序列长度大于1:nums[i]可以跟在前面任何一个数后面形成子序列。设前面的某一个数的下标为j其中 0ji-1 。只要nums[j]nums[i]i位置元素跟在j元素后面就可以形成递增序列长度为dp[j]1。因此我们仅需找到满足要求的最大的dp[j]1 即可。综上, dp[i]max(dp[j] 1,dp[i])其中0 j i-1 nums[j] nums[i] 。3.初始化:所有的元素「单独」都能构成一个递增子序列因此可以将dp表内所有元素初始化为1。由于用到前面的状态因此我们循环的时候从第二个位置开始即可。4.填表顺序:显而易见填表顺序「从左往右」。5.返回值:由于不知道最长递增子序列以谁结尾因此返回dp表里面的「最大值」。C算法代码class Solution { public: int lengthOfLIS(vectorint nums) { int n nums.size(); vectorint dp(n, 1); for(int i 1; i n; i) { for(int j i - 1; j 0; j--) { if(nums[i] nums[j]) { dp[i] max(dp[i], dp[j] 1); } } } int ret INT_MIN; for(int i 0; i n; i) { ret max(ret, dp[i]); } return ret; } };算法总结及流程解析28.摆动序列题目链接376. 摆动序列 - 力扣LeetCode题目描述题目示例解法(动态规划):算法思路:1.状态表示:对于线性dp我们可以用「经验题目要求」来定义状态表示i.以某个位置为结尾巴拉巴拉;ii.以某个位置为起点巴拉巴拉。这里我们选择比较常用的方式以某个位置为结尾结合题目要求定义一个状态表示dp[i]表示「以i位置为结尾的最长摆动序列的长度」。但是问题来了如果状态表示这样定义的话以位置为结尾的最长摆动序列的长度我们没法从之前的状态推导出来。因为我们不知道前一个最长摆动序列的结尾处是递增的还是递减的。因此我们需要状态表示能表示多一点的信息:要能让我们知道这一个最长摆动序列的结尾是递增的还是递减的。解决的方式很简单:搞两个dp表就好了。f[i]表示以i位置元素为结尾的所有的子序列中最后一个位置呈现「上升趋势」的最长摆动序列的长度;g[i]表示以i位置元素为结尾的所有的子序列中最后一个位置呈现「下降趋势」的最长摆动序列的长度。2.状态转移方程由于子序列的构成比较特殊i位置为结尾的子序列前一个位置可以是[0i-1]的任意位置因此设j为[0i-1]区间内的某一个位置。对于f[i]我们可以根据「子序列的构成方式」进行分类讨论i.子序列长度为1:只能自己玩了此时f[i]1 ;ii.子序列长度大于1:因为结尾要呈现上升趋势因此需要nums[j]nums[i]。在满足这个条件下j结尾需要呈现下降状态最长的摆动序列就是g[j]1。因此我们要找出所有满足条件下的最大的g[j]1 。综上f[i]max(g[j] 1f[i])注意使用g[j]时需要判断。对于g[i]我们可以根据「子序列的构成方式」进行分类讨论i.子序列长度为1只能自己玩了此时g[i]1 ;ii.子序列长度大于1因为结尾要呈现下降趋势因此需要nums[j]nums[i]。在满足这个条件下j结尾需要呈现上升状态因此最长的摆动序列就是f[j]1 。因此我们要找出所有满足条件下的最大的f[j]1 。综上g[i] max(f[j] 1g[i])注意使用f[j]时需要判断。3.初始化:所有的元素「单独」都能构成一个摆动序列因此可以将dp表内所有元素初始化为1。4.填表顺序:毫无疑问是「从左往右」。5.返回值:应该返回「两个dp表里面的最大值」我们可以在填表的时候顺便更新一个「最大值」。C算法代码class Solution { public: int wiggleMaxLength(vectorint nums) { int n nums.size(); vectorint up_dp(n, 1); vectorint down_dp(n, 1); for(int i 1; i n; i) { for(int j i - 1; j 0; j--) { if(nums[i] nums[j]) { up_dp[i] max(up_dp[i], down_dp[j] 1); } else if(nums[i] nums[j]) { down_dp[i] max(down_dp[i], up_dp[j] 1); } } } int ret INT_MIN; for(int i 0; i n; i) { ret max(max(ret, up_dp[i]), down_dp[i]); } return ret; } };算法总结及流程解析结束语到此27.最长递增子序列28.摆动序列 这两道算法题就讲解完了。最长递增子序列问题采用dp[i]表示以i结尾的最长子序列长度通过双层循环比较元素值进行状态转移摆动序列问题则使用两个dp数组(f[i]和g[i])分别记录以i结尾的上升和下降趋势序列长度通过判断相邻元素大小关系进行状态转移。希望大家能有所收获