《算法题讲解指南：动态规划算法--子序列问题》--29.最长递增子序列的个数，30.最长数对链，31.最长定差子序列

小叶-duck个人主页❄️个人专栏《Data-Structure-Learning》《C入门到进阶自我学习过程记录》《算法题讲解指南》--优选算法《算法题讲解指南》--递归、搜索与回溯算法《算法题讲解指南》--动态规划算法✨未择之路不须回头已择之路纵是荆棘遍野亦作花海遨游目录29.最长递增子序列的个数题目链接题目描述题目示例解法(动态规划)算法思路C算法代码算法总结及流程解析30.最长数对链题目链接题目描述题目示例解法(动态规划)算法思路C算法代码算法总结及流程解析31.最长定差子序列题目链接题目描述题目示例解法(动态规划)算法思路C算法代码算法总结及流程解析结束语29.最长递增子序列的个数题目链接673. 最长递增子序列的个数 - 力扣LeetCode题目描述题目示例解法(动态规划)算法思路1.状态表示先尝试定义一个状态:以为结尾的最长递增子序列的「个数」。那么问题就来了我都不知道以i为结尾的最长递增子序列的「长度」是多少我怎么知道最长递增子序列的个数呢?因此我们解决这个问题需要两个状态一个是「长度」一个是「个数」len[i]表示以i为结尾的最长递增子序列的长度;count[i]表示以i为结尾的最长递增子序列的个数。2.状态转移方程求个数之前我们得先知道长度因此先看len[i]i.在求i 结尾的最长递增序列的长度时我们已经知道 [0i-1] 区间上的 len[j] 信息用 j 表示[0i-1]区间上的下标;ii.我们需要的是递增序列因此[0i-1]区间上的 nums[j]只要能和 nums[i]构成上升序列那么就可以更新dp[i]的值此时最长长度为dp[j]1;iii.我们要的是[0i-1]区间上所有情况下的最大值。综上所述对于几en[i]我们可以得到状态转移方程为len[i] max(len[j] 1,len[i])其中0 j i,并且nums[j] nums[i] 。在知道每一个位置结尾的最长递增子序列的长度时我们来看看能否得到count[i]i.我们此时已经知道len[i]的信息还知道[i-1]区间上的count[j]信息用j表示[0i-1]区间上的下标;ii.我们可以再遍历一遍[0i1]区间上的所有元素只要能够构成上升序列并且上升序列的长度等于dp[i]那么我们就把count[i]加上count[j]的值。这样循环一遍之后count[i]存的就是我们想要的值。综上所述对于count[i]我们可以得到状态转移方程为count[i] count[j]其中 j i并且nums[j] nums[i] dp[j] 1 dp[i]。3.初始化对于len[i]所有元素自己就能构成一个上升序列直接全部初始化为1;对于count[i]如果全部初始化为1在累加的时候可能会把「不是最大长度的情况」累加进去因此我们可以先初始化为0然后在累加的时候判断一下即可。具体操作情况看代码~4.填表顺序毫无疑问是「从左往右」。5.返回值用manLen 表示最终的最长递增子序列的长度。根据题目要求我们应该返回所有长度等于maxLen的子序列的个数。C算法代码class Solution { public: int findNumberOfLIS(vectorint nums) { int n nums.size(); vectorint len_dp(n, 1); vectorint count_dp(n, 1); int len 1; int count 1; for(int i 1; i n; i) { for(int j i - 1; j 0; j--) { if(nums[i] nums[j]) { // len_dp[i] max(len_dp[i], len_dp[j] 1); if(len_dp[i] len_dp[j] 1) { len_dp[i] len_dp[j] 1; count_dp[i] count_dp[j]; } else { if(len_dp[i] len_dp[j] 1) { count_dp[i] count_dp[j]; } } } } if(len len_dp[i]) { len len_dp[i]; count count_dp[i]; } else { if(len len_dp[i]) { count count_dp[i]; } } } // int len 0; // int count 0; // for(int i 0; i n; i) // { // if(len len_dp[i]) // { // len len_dp[i]; // count count_dp[i]; // } // else // { // if(len len_dp[i]) // { // count count_dp[i]; // } // } // } return count; } };算法总结及流程解析30.最长数对链题目链接646. 最长数对链 - 力扣LeetCode题目描述题目示例解法(动态规划)算法思路这道题目让我们在数对数组中挑选出来一些数对组成一个呈现上升形态的最长的数对链。像不像我们整数数组中挑选一些数让这些数组成一个最长的上升序列?因此我们可以把问题转化成我们学过的一个模型300.最长递增子序列。因此我们解决问题的方向应该在「最长递增子序列」这个模型上。不过与整形数组有所区别。在用动态规划结局问题之前应该先把数组排个序。因为我们在计算dp[i]的时候要知道所有左区间比pairs[i]的左区间小的链对。排完序之后只用「往前遍历一遍」即可。1.状态表示dp[i]表示以i 位置的数对为结尾时最长数对链的长度。2.状态转移方程对于dp[i]遍历所有[0i-1]区间内数对用j表示下标找出所有满足pairs[j][1]pairs[i][0]的j。找出里面最大的dp[j]然后加上1 就是以i位置为结尾的最长数对链。3.初始化刚开始的时候全部初始化为1。4.填表顺序根据「状态转移方程」填表顺序应该是「从左往右」。5.返回值根据「状态表示」返回整个dp表中的最大值。C算法代码class Solution { public: int findLongestChain(vectorvectorint pairs) { sort(pairs.begin(), pairs.end()); int n pairs.size(); vectorint dp(n, 1); int ret 1; for(int i 1; i n; i) { for(int j i - 1; j 0; j--) { if(pairs[j][1] pairs[i][0]) { dp[i] max(dp[i], dp[j] 1); } } ret max(ret, dp[i]); } // int ret 0; // for(int i 0; i n; i) // { // ret max(ret, dp[i]); // } return ret; } };算法总结及流程解析31.最长定差子序列题目链接1218. 最长定差子序列 - 力扣LeetCode题目描述题目示例解法(动态规划)算法思路这道题和300.最长递增子序列有一些相似但仔细读题就会发现本题的 arr.lenght 高达10^5 使用 O(N^2) 的 lcs 模型一定会超时。那么它有什么信息是300.最长递增子序列的呢? 是定差。之前我们只知道要递增不知道前一个数应当是多少就会导致可能前面的值忽大忽小所以我们需要把前面所有情况遍历一遍才能找到最大值现在我们可以计算出前一个数具体是多少了就可以用数值来定义dp数组的值并形成状态转移。这样就把已有信息有效地利用了起来。1.状态表示dp[i]表示以i位置的元素为结尾所有的子序列中最长的等差子序列的长度。2.状态转移方程:对于dp[i]上一个定差子序列的取值定为arr[i]-difference 。只要找到以上一个数字为结尾的定差子序列长度的dp[arr[i]-difference]然后加上1就是以i为结尾的定差子序列的长度。因此这里可以选择使用哈希表做优化。我们可以把「元素dp[j]」绑定放进哈希表中。甚至不用创建 dp 数组直接在哈希表中做动态规划。3.初始化刚开始的时候需要把第一个元素放进哈希表中hash[arr[0]]1 。4.填表顺序根据「状态转移方程」填表顺序应该是「从左往右」。5.返回值根据「状态表示」返回整个 dp 表中的最大值。C算法代码class Solution { public: int longestSubsequence(vectorint arr, int difference) { //创建一个哈希表利用哈希表实现动态规划 unordered_mapint, int hash; //arr[i] - dp[i] hash[arr[0]] 1; //初始化 int ret 1; for(int i 1; i arr.size(); i) { // if(hash[arr[i] - difference]) // { // hash[arr[i]] hash[arr[i] - difference] 1; // } // else // { // hash[arr[i]] 1; // } hash[arr[i]] hash[arr[i] - difference] 1; //如果arr[i] - difference在前面不存在则hash映射的值为0 //加上1也正好符合要求不需要额外判断 ret max(ret, hash[arr[i]]); } // int ret 0; // for(int i 0; i arr.size(); i) // { // ret max(ret, hash[arr[i]]); // } return ret; } };算法总结及流程解析结束语到此29.最长递增子序列的个数30.最长数对链31.最长定差子序列 这三道算法题就讲解完了。最长递增子序列个数通过维护长度和个数两个状态数组统计满足条件的序列数量.最长数对链转化为LIS问题并排序预处理最长定差子序列利用哈希表优化查找过程。三题均采用动态规划思想通过定义状态、转移方程、初始化和填表顺序解决问题其中第一题需同时跟踪长度和数量信息第三题利用哈希表实现O(1)查找。希望大家能有所收获