Day46 | 动态规划 ：线性DP 最长递增子序列&&最长连续递增子序列
动态规划应该如何学习？-CSDN博客
本次题解参考自灵神的做法，大家也多多支持灵神的题解
最长递增子序列【基础算法精讲 20】_哔哩哔哩_bilibili
动态规划学习：
1.思考回溯法（深度优先遍历）怎么写
注意要画树形结构图
2.转成记忆化搜索
看哪些地方是重复计算的，怎么用记忆化搜索给顶替掉这些重复计算
3.把记忆化搜索翻译成动态规划
基本就是1:1转换
文章目录
- Day46 | 动态规划 ：线性DP 最长递增子序列&&最长连续递增子序列
- 300.最长递增子序列
- 思路分析（子问题）:
- 1.回溯 DFS
- 2.记忆化搜索
- 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 {0<j<i}
加1加的是nums[i]本身
举个例子：
我们的i如果是5的话，nums[i]=7，枚举比它小的，即i=4,3,2 nums[i]=3,5,2
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
dfs(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,vector<int>& nums)
2.终止条件
终止条件就是i<0，即子序列里面没有数字了
i<0我们的程序本身也不会执行，所以不需要终止条件
3.本层逻辑
我们以nums[i]结尾的最长递增子序列的长度不需要看i以后的数，所以每次从0-i进行枚举，如果比nums[i]才会继续往下选
我们一次dfs(i)算出来的是以nums[i]为结尾的最长子序列的长度
每一层递归函数向上返回的时候，由于我们是以nums[i]为结尾的最长递增子序列，所以长度最小为1，就是nums[i]本身，所以返回的时候要+1，加的就是自身
然后在主函数中遍历一遍nums数组，把所有的i都传一遍，挑出里面的最大值
int dfs(int i,vector<int>& nums)
{
int res=0;
for(int j=0;j<i;j++)
if(nums[j]<nums[i])
res=max(res,dfs(j,nums));
return res+1;
}
int lengthOfLIS(vector<int>& nums) {
int res=0;
for(int i=0;i<nums.size();i++)
res=max(res,dfs(i,nums));
return res;
}
完整代码：
当然，这是超时的
class Solution {
public:
int dfs(int i,vector<int>& nums)
{
int res=0;
for(int j=0;j<i;j++)
if(nums[j]<nums[i])
res=max(res,dfs(j,nums));
return res+1;
}
int lengthOfLIS(vector<int>& nums) {
int res=0;
for(int i=0;i<nums.size();i++)
res=max(res,dfs(i,nums));
return res;
}
};
2.记忆化搜索
就是搞一个哈希表dp，全都初始化为-1，每次返回前给哈希表dp赋值，碰到不是-1的那就是算过的，那就直接返回计算过的结果，不需要再次递归了
class Solution {
public:
int dfs(int i,vector<int>& nums,vector<int>& dp)
{
if(dp[i]!=0)
return dp[i];
int res=0;
for(int j=0;j<i;j++)
if(nums[j]<nums[i])
res=max(res,dfs(j,nums,dp));
return dp[i]=res+1;
}
int lengthOfLIS(vector<int>& nums) {
vector<int> dp(nums.size(),0);
int res=0;
for(int i=0;i<nums.size();i++)
res=max(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]自身就算一个长度
vector<int> dp(nums.size(),1);
4.确定遍历顺序
后续结果需要依赖前面的计算结果，故使用从前往后遍历
然后在计算的时候记录一下最大值，最后返回最大值就好
for(int i=0;i<nums.size();i++)
{
for(int j=0;j<i;j++)
if(nums[j]<nums[i])
dp[i]=max(dp[i],dp[j]+1);
if(dp[i]>res)
res=dp[i];
}
完整代码
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> dp(nums.size(),1);
int res=0;
for(int i=0;i<nums.size();i++)
{
for(int j=0;j<i;j++)
if(nums[j]<nums[i])
dp[i]=max(dp[i],dp[j]+1);
if(dp[i]>res)
res=dp[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,vector<int>& nums)
{
if(i<0)
return 0;
if(i>0&&nums[i-1]<nums[i])
return dfs(i-1,nums)+1;
else
return 1;
}
int findLengthOfLCIS(vector<int>& nums) {
int res=0;
for(int i=0;i<nums.size();i++)
res=max(res,dfs(i,nums));
return res;
}
};
2.记忆化搜索
老样子还是返回前进行赋值就好
class Solution {
public:
int dfs(int i,vector<int>& nums,vector<int>& dp)
{
if(dp[i]!=-1)
return dp[i];
if(i>0&&nums[i-1]<nums[i])
return dp[i]=dfs(i-1,nums,dp)+1;
else
return dp[i]=1;
}
int findLengthOfLCIS(vector<int>& nums) {
int res=0;
vector<int> dp(nums.size(),-1);
for(int i=0;i<nums.size();i++)
res=max(res,dfs(i,nums,dp));
return res;
}
};
3.动态规划
class Solution {
public:
int findLengthOfLCIS(vector<int>& nums) {
int res=1;
vector<int> dp(nums.size(),1);
for(int i=1;i<nums.size();i++)
{
if(nums[i]>nums[i-1])
dp[i]=dp[i-1]+1;
res=max(res,dp[i]);
}
return res;
}
};
