Day46 | 动态规划 ：线性DP 最长递增子序列

动态规划应该如何学习？-CSDN博客

本次题解参考自灵神的做法，大家也多多支持灵神的题解

最长递增子序列【基础算法精讲 20】_哔哩哔哩_bilibili

动态规划学习：

1.思考回溯法（深度优先遍历）怎么写

注意要画树形结构图

2.转成记忆化搜索

看哪些地方是重复计算的，怎么用记忆化搜索给顶替掉这些重复计算

3.把记忆化搜索翻译成动态规划

基本就是1:1转换

300.最长递增子序列

300. 最长递增子序列 - 力扣（LeetCode）

思路分析（子问题）:

dfs(i)表示以nums[i]结尾的最长递增子序列的长度

我们往前找，只有找到比nums[i]小的nums[j]才往下递归，否则不进行递归

我们一次dfs(i)可以找出以nums[i]结尾的最长递增子序列的长度

1
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

1
2
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
1
dfs(5)=max(dfs(4),dfs(3),dfs(2))+1

这样即可以把最长的情况枚举出来，还可以避免遗漏，因为每一次dfs我们都只找以nums[i]结尾的最长的递增子序列

如果以7结尾的话，那就是2,3,7

如果我们要再找以18结尾的

那就是

1
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]结尾的最长递增子序列的长度

1
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都传一遍，挑出里面的最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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;
   }

完整代码：

当然，这是超时的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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的那就是算过的，那就直接返回计算过的结果，不需要再次递归了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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中也是对应的

1
dp[i]=max(dp[i],dp[j]+1);

3.dp数组如何初始化

都初始化为1是因为nums[i]自身就算一个长度

1
vector<int> dp(nums.size(),1);

4.确定遍历顺序

后续结果需要依赖前面的计算结果，故使用从前往后遍历

然后在计算的时候记录一下最大值，最后返回最大值就好

1
2
3
4
5
6
7
8
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];
      }

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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的子序列就好

1
dfs(i)=dfs(i-1)+1;

1.回溯法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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.记忆化搜索

老样子还是返回前进行赋值就好

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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.动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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;
    }
};