leetcode-1143-线性DP-最长公共子序列

发表于 | 分类于

题目

1.png

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        if(text1.empty() || text2.empty()) return 0;
        int len1 = text1.size();
        int len2 = text2.size();

        // 对于 text1[1..i] 和 text2[1..j]，它们的 LCS 长度是 dp[i][j]
        vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));

        for(int i = 1; i <= len1; ++i)
            for(int j = 1; j <= len2; ++j)
                if(text1[i-1] == text2[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[len1][len2];
        }
};