力扣第44天----第1143题、第1035题、第53题

# 力扣第44天----第1143题、第1035题

一、第1143题–最长公共子序列

​ 上一题是，dp[i][j] 与 dp[i-1][j-1]建立关系。这题是dp[i][j] 与 dp[i-1][j-1]、dp[i][j-1]、dp[i-1][j]建立递推关系。

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        vector> dp(text1.size()+1, vector(text2.size() + 1, 0));
        for(int i =1; i<=text1.size(); ++i){
            for (int j =1; j<=text2.size(); ++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[text1.size()][text2.size()];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

二、第1035题–不相交的线

​ 套了个壳子，实际跟上一题一模一样。

class Solution {
public:
    int maxUncrossedLines(vector& nums1, vector& nums2) {
        vector> dp(nums1.size()+1, vector(nums2.size() + 1, 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]);
            }
        }
        return dp[nums1.size()][nums2.size()];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13