代码随想录训练营打卡第36天：动态规划解决子序列问题

1.300最长递增子序列

1.问题描述

找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。

2.问题转换

从nums[0...i]的最长的递增的子序列

3.解题思路

1. 每一个位置的nums[i]都有两种状态：是否放入
2. 对于放入状态：找到从[0..j](j<i)之间的递增子序列，如果满足递增，放入子序列中，找到其中最长的那个递增子序列，更新长度。
3. 对于不放入状态：如果不满足递增，则不放入。

4.为什么使用动态规划？

因为从[0..i]的最长的递增子序列状态一定是由[0..j]的状态递推出来，所以考虑使用动态规划的方法。

5.动态规划的具体实现

1. dp[j]数组的含义：代表的是从nums[0..j]的最长递增子序列。
2. 递推公式：for(int i = 0;i<j;i++){        if(nums[j]>nums[i]){//首先需要满足递增                    dp[j] = max(dp[j],dp[i]+1);//从中选择最长的作为最长递增子序列.dp[i] +1:其中i可以等效为背包问题里面的j-weight[i],1可以等效为背包问题里面的value[i].              }          }
3. 初始化：默认情况下每个的都是1，因为自身可以当做唯一的那一个递增子序列。
4. 遍历顺序：由递推公式可以知道，应该是满足从小到大的方式进行遍历。

6.进阶：使用动态规划和二分法来解决

1.思路

我们使用一个数组tail用来存放从[0..i]的单调递增数组的尾数（而且对应的nums[i]越小越好），tail[i]代表的是尾数，i代表的是长度。

2.具体实现

1.遍历数组得到此时的nums[i],根据nums[i]在tail数组中找到能够满足的最左侧的位置。

2.最左侧的位置的查找：使用二分法来找到满足严格递增的最长的长度。可能会出现两种情况：

        1.left<res(即在tails的范围内)当tails[mid]<nums[i],tails[left]>nums[i]:此时将tails[left] = nums[i],可以保证在后面运行的时候能够尽可能的找到更长的长度。

        2.当left == res（即这个数比最右侧的那个递增的都长）。此时res++;tails[left] = nums[i].

3.最后的返回值就是对应的一个res的长度。

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        /*//方法1：动态规划
        int n = nums.size();
        vector<int> dp(n,1);//dp[j]:从0-j数组的最长的递增子序列
        int result = 1;
        for(int j = 1;j<n;j++){
            for(int i = 0;i<j;i++){
                if(nums[j]>nums[i]){
                    dp[j] = max(dp[j],dp[i]+1);
                }
            }
            if(result<dp[j])result = dp[j];
        }
        return result;
        */
        //方法2：动态规划+二分查找
        int n = nums.size();
        vector<int> tails(n,0);//用来存放一个单调递增的数组的尾数
        int res = 0;//代表的是单调递增的最大长度
        for(auto num:nums){
            //用于在tail数组中找到需要替换的那个位置tails[i]<num<tails[i+1],此时将其替换为tails[i+1] = num;
            //如果这个值在这个里面找不到，就放在最右边,同时res++;
            int left = 0,right = res;
            while(left<right){//[left,right)循环不变量
                int mid = left +(right - left)/2;
                if(tails[mid]<num)left = mid+1;
                else right = mid;
            }
            tails[left] = num;
            if(res == right) res++;
        }
        return res;

    }
};

2.647最长连续递增子序列

1.问题描述

找到其中最长连续递增子序列的长度。

2.问题转换

从nums[0...i]的最长的连续递增的子序列

3.解题思路

1. 每一个位置的nums[i]都有两种状态：是否放入
2. 对于放入状态：nums[i]>nums[i-1],则放入。
3. 对于不放入状态：如果不满足递增，则不放入。

4.为什么使用动态规划？

因为从[0..i]的最长的递增子序列状态一定是由前一个的状态递推出来，所以考虑使用动态规划的方法。

5.动态规划的具体实现

1. dp[j]数组的含义：代表的是从nums[0..j]的最长连续递增子序列。（也可以将其表示为以i为结尾的最长的连续递增子序列，然后求解得到最大值）
2. 递推公式：if(nums[i]>nums[i-1]){//满足递增才能添加
                   tail[i] = tail[i-1]+1;
               }//if(result>tail[i])tail[i] = result;//比较找到最大值
3. 初始化：默认情况下每个的都是1，因为自身可以当做唯一的那一个递增子序列。
4. 遍历顺序：由递推公式可以知道，应该是满足从小到大的方式进行遍历。

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        int n = nums.size();
        //vector<int> dp(n,1);
        vector<int> tail(n,1);
        int result = 1;
        int i = 0;
        for(int i = 1;i<n;i++){
            if(nums[i]>nums[i-1]){
                tail[i] = tail[i-1]+1;
            }
        }
        auto maxs =  max_element(tail.begin(),tail.end());
        return *maxs;
        /*
        for(int j = 1;j<n;j++){
            i = j;
            for(;i>0;i--){
                if(nums[i]<=nums[i-1]){
                    break;
                }
            }
            dp[j] = max(dp[j-1],(j-i+1));//长度
        }
        return dp[n-1];*/
    }
};

3.718最长重复子数组

1.问题描述

找到其中最长重复子数组的长度。

2.问题转换

按照顺序遍历，如果相同了就长度+1

3.解题思路

1. 每一个位置的nums[i]都有两种状态：是否相等
2. 对于相等状态：即nums1[i-1] == nums2[j-1],此时长度+1，然后比较最大值，更新res
3. 对于不相等状态：比较最大值更新res
4. 将最大值存放在res中

4.为什么使用动态规划？

因为每一个位置的值都可以由前面的状态或者当前的状态确定。

5.动态规划的具体实现

1. dp[i][j]数组的含义：代表的是从nums1[0..i-1],nums2[0..j-1]的重复子数组长度。（
2. 递推公式： if(nums1[i-1] == nums2[j-1]){dp[i][j] = dp[i-1][j-1]+1;}
3. 初始化：默认情况下每个的都是1，因为自身可以当做唯一的那一个递增子序列。
4. 遍历顺序：由递推公式可以知道，应该是满足从小到大的方式进行遍历。
5. 最终结果存放在res中，因为res的含义是最长的重复子数组的长度。

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size();
        int n = nums2.size();
        vector<vector<int>> dp(m+1,vector<int>(n+1,0));
        int res = 0;
        for(int i = 1;i<m+1;i++){
            for(int j = 1;j<n+1;j++){
                if(nums1[i-1] == nums2[j-1]){
                    dp[i][j] = dp[i-1][j-1]+1;
                }
                if(dp[i][j]>res) res = dp[i][j];
            }
            
        }
        return res;
    }
};