网站建站网站设计,辽宁建设工程信息网报名步骤,保定网站建设方案推广,网站后台无ftpDay46 | 动态规划 #xff1a;线性DP 最长递增子序列最长连续递增子序列
动态规划应该如何学习#xff1f;-CSDN博客
本次题解参考自灵神的做法#xff0c;大家也多多支持灵神的题解
最长递增子序列【基础算法精讲 20】_哔哩哔哩_bilibili
动态规划学习#…Day46 | 动态规划 线性DP 最长递增子序列最长连续递增子序列
动态规划应该如何学习-CSDN博客
本次题解参考自灵神的做法大家也多多支持灵神的题解
最长递增子序列【基础算法精讲 20】_哔哩哔哩_bilibili
动态规划学习
1.思考回溯法深度优先遍历怎么写
注意要画树形结构图
2.转成记忆化搜索
看哪些地方是重复计算的怎么用记忆化搜索给顶替掉这些重复计算
3.把记忆化搜索翻译成动态规划
基本就是1:1转换 文章目录 Day46 | 动态规划 线性DP 最长递增子序列最长连续递增子序列300.最长递增子序列思路分析子问题:1.回溯 DFS2.记忆化搜索3.1:1翻译为动态规划 674.最长连续递增序列思路1.回溯法2.记忆化搜索3.动态规划 300.最长递增子序列
300. 最长递增子序列 - 力扣LeetCode
思路分析子问题:
dfs(i)表示以nums[i]结尾的最长递增子序列的长度
我们往前找只有找到比nums[i]小的nums[j]才往下递归否则不进行递归
我们一次dfs(i)可以找出以nums[i]结尾的最长递增子序列的长度
dfs(i)max(dfs(j))1 {0ji}加1加的是nums[i]本身
举个例子
我们的i如果是5的话nums[i]7枚举比它小的即i4,3,2 nums[i]3,5,2
输入nums [10,9,2,5,3,7,101,18]
输出4dfs(5)max(dfs(4),dfs(3),dfs(2))1这样即可以把最长的情况枚举出来还可以避免遗漏因为每一次dfs我们都只找以nums[i]结尾的最长的递增子序列
如果以7结尾的话那就是2,3,7
如果我们要再找以18结尾的
那就是
dfs(7)max(dfs(5),dfs(4),dfs(3),dfs(2),dfs(1),dfs(0))1如果大家没有听太懂的话建议看看灵神的视频知道那个意思但是我也不知道该怎么讲
1.回溯 DFS
1.返回值和参数
i是数组下标我们最长递增子序列的最后一个数就是nums[i]
dfs(i)表示以nums[i]结尾的最长递增子序列的长度
int dfs(int i,vectorint nums)2.终止条件
终止条件就是i0即子序列里面没有数字了
i0我们的程序本身也不会执行所以不需要终止条件
3.本层逻辑
我们以nums[i]结尾的最长递增子序列的长度不需要看i以后的数所以每次从0-i进行枚举如果比nums[i]才会继续往下选
我们一次dfs(i)算出来的是以nums[i]为结尾的最长子序列的长度
每一层递归函数向上返回的时候由于我们是以nums[i]为结尾的最长递增子序列所以长度最小为1就是nums[i]本身所以返回的时候要1加的就是自身
然后在主函数中遍历一遍nums数组把所有的i都传一遍挑出里面的最大值 int dfs(int i,vectorint nums){int res0;for(int j0;ji;j)if(nums[j]nums[i])resmax(res,dfs(j,nums));return res1;}int lengthOfLIS(vectorint nums) {int res0;for(int i0;inums.size();i)resmax(res,dfs(i,nums));return res;}完整代码
当然这是超时的
class Solution {
public:int dfs(int i,vectorint nums){int res0;for(int j0;ji;j)if(nums[j]nums[i])resmax(res,dfs(j,nums));return res1;}int lengthOfLIS(vectorint nums) {int res0;for(int i0;inums.size();i)resmax(res,dfs(i,nums));return res;}
};2.记忆化搜索
就是搞一个哈希表dp全都初始化为-1每次返回前给哈希表dp赋值碰到不是-1的那就是算过的那就直接返回计算过的结果不需要再次递归了
class Solution {
public:int dfs(int i,vectorint nums,vectorint dp){if(dp[i]!0)return dp[i];int res0;for(int j0;ji;j)if(nums[j]nums[i])resmax(res,dfs(j,nums,dp));return dp[i]res1;}int lengthOfLIS(vectorint nums) {vectorint dp(nums.size(),0);int res0;for(int i0;inums.size();i)resmax(res,dfs(i,nums,dp));return res;}
};3.1:1翻译为动态规划
1.确定dp数组以及下标的含义
dp[i]就是以nums[i]结尾的最长递增子序列的长度
2.确定递推公式
和dfs中也是对应的
dp[i]max(dp[i],dp[j]1);3.dp数组如何初始化
都初始化为1是因为nums[i]自身就算一个长度
vectorint dp(nums.size(),1);4.确定遍历顺序
后续结果需要依赖前面的计算结果故使用从前往后遍历
然后在计算的时候记录一下最大值最后返回最大值就好 for(int i0;inums.size();i){for(int j0;ji;j)if(nums[j]nums[i])dp[i]max(dp[i],dp[j]1);if(dp[i]res)resdp[i];}完整代码
class Solution {
public:int lengthOfLIS(vectorint nums) {vectorint dp(nums.size(),1);int res0;for(int i0;inums.size();i){for(int j0;ji;j)if(nums[j]nums[i])dp[i]max(dp[i],dp[j]1);if(dp[i]res)resdp[i];}return res;}
};674.最长连续递增序列
674. 最长连续递增序列 - 力扣LeetCode
思路
这个就比较简单了选或不选的思路就行,dfs(i)表示以nums[i]结尾的最长连续递增子序列
我们nums[i-1]nums[i]就选nums[i]否则的话就返回个1表示是nums[i]本身这个数是一个长度为1的子序列就好
dfs(i)dfs(i-1)1;1.回溯法
class Solution {
public:int dfs(int i,vectorint nums){if(i0)return 0;if(i0nums[i-1]nums[i])return dfs(i-1,nums)1;elsereturn 1;}int findLengthOfLCIS(vectorint nums) {int res0;for(int i0;inums.size();i)resmax(res,dfs(i,nums));return res;}
};2.记忆化搜索
老样子还是返回前进行赋值就好
class Solution {
public:int dfs(int i,vectorint nums,vectorint dp){if(dp[i]!-1)return dp[i];if(i0nums[i-1]nums[i])return dp[i]dfs(i-1,nums,dp)1;elsereturn dp[i]1;}int findLengthOfLCIS(vectorint nums) {int res0;vectorint dp(nums.size(),-1);for(int i0;inums.size();i)resmax(res,dfs(i,nums,dp));return res;}
};3.动态规划
class Solution {
public:int findLengthOfLCIS(vectorint nums) {int res1;vectorint dp(nums.size(),1);for(int i1;inums.size();i){if(nums[i]nums[i-1])dp[i]dp[i-1]1;resmax(res,dp[i]);}return res;}
};
