【代码随想录day44】【C++复健】1143.最长公共子序列；1035.不相交的线；53. 最大子序和；392. 判断子序列

1143.最长公共子序列

本题一开始以为是和前面那个一维递增子序列一样，dp数组的[i][j]表示的是以i，j为结尾的最长公共子序列，然后用两个for循环去前面找前缀对应的最大值，这样写出来的代码算上遍历总共要4次for循环，结果当然是会超时，并且我的代码还不知道哪里有问题，得不到正确的结果。

那么为什么本题用的是卡哥那样的定义方法，即：
1 如果当前位置相同，就是i-1，j-1位置的值+1
2 否则，取i-1，j和i，j-1的最大值。

这里引用一段在b站看到的评论的解释，由文无cc_大佬提供：

求递增序列的时候，因为要求序列有序，所以必须确定序列最后一个元素的值，才能比较新加入序列的元素是不是递增的。求相等序列的时候，如果求连续相等子序列，则还是要确定序列最后一个元素的值；但是本题求的是不必连续的相等子序列，就不需要知道序列最后一个元素的值，只要知道范围内相等的序列长度就行，新来的相等元素可以直接加在序列后面

也就是说我在算最长公共子序列的时候，是不需要去看序列最后一个元素到底是什么的，所以也就无需将dp数组定义成以i，j为结尾。

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.size();
        int n = text2.size();
        vector<vector<int>> dp(m+1, vector<int>(n+1));
        for(int i=1; i<=m; i++){
            for(int j=1; j<=n; j++){
                if(text1[i-1] == text2[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }
                else{
                    dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
                }
            }
        }
        return dp[m][n];
    }
};

1035.不相交的线

还真和上一题一模一样，错的也一一模一样：比较的时候要判断nums1[i-1] == nums2[j-1]而不是nums1[i] == nums2[j]，隔了一会再写就又忘了。

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));
        for(int i=1; i<=m; i++){
            for(int j=1; j<=n; 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数组，写出来就是对的。解析里说dp比较直观，贪心比较难想，但我感觉这俩是一模一样的思路，只是写法不一样而已。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n);
        dp[0] = nums[0];
        if(n==1){
            return nums[0];
        }
        int result = dp[0];
        for(int i=1; i<n; i++){
            dp[i] = max(dp[i-1]+nums[i], nums[i]);
            if(dp[i] > result){
                result = dp[i];
            }
        }
        return result;
        }
};

392. 判断子序列

本题也是一样，满脑子双指针，让我用dp写一个m*n复杂度的代码感觉就像杀了我一样难受，总是感觉这里能优化，那里能改一下，结果改了半天，循环逻辑倒是解决了，但是一些特殊的初始化和边界条件又出现问题了。
最后老老实实写了一个m*n复杂度的代码，还是这个适合我，之前简化了半天完全给自己绕进去了。

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int m = s.size();
        int n = t.size();
        if(m==0){return true;}
        vector<vector<int>> dp(m+1, vector<int>(n+1));
        for(int i=1; i<=m; i++){
            for(int j=1; j<=n; j++){
                if(s[i-1] == t[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }
                else{
                    dp[i][j] = dp[i][j-1];
                }
            } 
        }
        return dp[m][n] == m;
    }
};