笔记：代码随想录算法训练营day44：LeetCode1143.最长公共子序列、1035.不相交的线、53. 最大子序和、392.判断子序列

思路：代码随想录

1143.最长公共子序列

力扣题目链接

思路：对于要求连续的，不相等就跳过去了，但是对于不要求连续的，不相等时对上一状态要有一个继承，后面能相等的话好续上，那这样写出来的话dp[i][j]虽然定义为nums1中0~（i-1）和nums2中0~（j-1）的公共子序列，但是公共子序列的结尾不一定是在i-1或j-1

// 定义：dp[i][j]的定义为，字符串s从0到i-1和字符串t从0到j-1的相同子序列的长度
class Solution {
public:
    bool isSubsequence(string s, string t) {
        vector<vector<int>> dp(s.size()+1,vector<int>(t.size()+1,0));
        for(int i=1;i<=s.size();i++){
            for(int j=1;j<=t.size();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];
            }
        }
        if(dp[s.size()][t.size()]==s.size()) return true;
        return false;
    }
};

1035.不相交的线

力扣题目链接

思路：跟上一题是一个意思，不过有一个小细节就是交叉问题，但其实这样顺着记录不会交叉，举一个简单的例子1，2和2，1模拟一下就可以了

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

53. 最大子序和

力扣题目链接

思路：和贪心思路类似，贪心是显性地用0来判断取舍，动规的判断位置相对贪心往后移了一位，直接以数值和来判断

定义：dp[i]表示前nums[i](含)之前的子序列的最大和

递推公式：dp[i]取算上前面的序列和 与 从不加前面的从当前开始计算的值 之间的最大值，定义一个result不断记录最大值，有点像贪心

初始化：第一个初始化为第一个数字

遍历顺序：从前向后

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

392.判断子序列

力扣题目链接

思路：和前面求 1143.最长公共子序列思路大致一致

区别在递推公式处，是删掉第二个数组中的数字去碰第一个数组，所以遍历到两个数字不相等的时候，不是比较dp[i][j-1]和dp[i-1][j],而是忽略掉当前的第二个数组的j-1处，直接等于从j-2处继承过来的值

// 定义：dp[i][j]的定义为，字符串s从0到i-1和字符串t从0到j-1的相同子序列的长度
class Solution {
public:
    bool isSubsequence(string s, string t) {
        vector<vector<int>> dp(s.size()+1,vector<int>(t.size()+1,0));
        for(int i=1;i<=s.size();i++){
            for(int j=1;j<=t.size();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];
            }
        }
        if(dp[s.size()][t.size()]==s.size()) return true;
        return false;
    }
};