代码随想录训练营day44|1143.最长公共子序列，1035.不相交的线, 53. 最大子序和,392.判断子序列

1143.最长公共子序列

这题并不要求连续
子序列的要求是可以删除某些元素，但不能改变顺序。
顺着上题的思路，这题也应该设立一个二维数组

 vector<vector<int>> dp(text1.size(),vector<int>(text2.size(),0));

dp[i][j]表示的是以text1[i]为结尾的字符串和以text2[j]为结尾的字符串的最长公共子序列。
如果text1[i]和text2[j]相等的话，则dp[i][j]=dp[i-1][j-1]+1;
(两个同时回退)
如果不相等的话
则应该考虑dp[i-1][j]和dp[i][j-1]中的最大值

if(text1[i]==text2[j])
    dp[i][j]=dp[i-1][j-1]+1;
    //如果相同同时回退
else{
    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}

初始化的时候要注意，如果text1[i]==text2[0]
则dp[i][0]=1；
如果不相等，则继承上一次的值，而不是为0.

for(int i=0;i<text1.size();i++){
    if(text1[i]==text2[0])
         dp[i][0]=1;
     else if(i>0){
         dp[i][0]=dp[i-1][0];
     }
 }
 for(int j=1;j<text2.size();j++){
     if(text2[j]==text1[0])
         dp[0][j]=1;
     else if(j>0)
         dp[0][j]=dp[0][j-1];
 }

看了一下力扣官解，也可以创造一个m+1和n+1大小的矩阵，这样就不用专门初始化。

1035.不相交的线

思路：只有两个数字相等时才连线，那其实就是找最长公共子数组。

class Solution {
public:
    int maxUncrossedLines(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));
        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;
                }
                else{
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
      

        return dp[m][n];
    }
};

53. 最大子序和

之前是用贪心写的，现在用动规写一遍
题目

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

392.判断子序列

题目
可以把它当成求最长公共子序列的长度来做，使得它==s.size();
我写了另一种定义：
dp[i][j]表示的是以s[i]为结尾的字符串是否是t[j]为结尾的字符串的子序列。

 vector<vector<bool>> dp(m,vector<bool>(n,false));

注意：1.j从i开始，因为j必须大于i的长度，才有可能s是j的子序列。2.由于这里明确给出了s是t的子序列，所有在i和j不相等时，只用删除j就可以，不能删除i

for(int i=0;i<m;i++){
   for(int j=i;j<n;j++){
        if(s[i]==t[j]){
            if(i>0&&j>0)
                dp[i][j]=dp[i-1][j-1];
            else
                dp[i][j]=true;
        }
        else{
            if(j>0)
                dp[i][j]=dp[i][j-1];
        }
            
    }
}

双指针

当然这题也可以用双指针来做