1143. 最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。 一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。 例如，”ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。 若这两个字符串没有公共子序列，则返回 0。 示例 1:

输入：text1 = “abcde”, text2 = “ace” 输出：3

解释：最长公共子序列是 “ace”，它的长度为 3。 示例 2:

输入：text1 = “abc”, text2 = “abc” 输出：3

解释：最长公共子序列是 “abc”，它的长度为 3。 示例 3:

输入：text1 = “abc”, text2 = “def” 输出：0

解释：两个字符串没有公共子序列，返回 0。 提示:

• 1 <= text1.length <= 1000
• 1 <= text2.length <= 1000
• 输入的字符串只含有小写英文字符。

解题思路

动态规划
dp数组的含义
dp[i][j]的含义是：对于text[0.....i-1]和text[0.......j-1]，它们的LCS的长度是dp[i][j]。
base base
让索引位0的行和列表示空串，dp[0][...]和dp[...][0]都应该初始位0，因为空串""和任意串如abc的LCS长度为0。
状态转移方程
如果s1[i] == s2[j]，说明这个字符一定在lcs中

所以推导逻辑
if (text1[i] == text2[j]) dp[i][j] = ``dp[i-1][j-1] + 1;

而如果s1[i] != s2[j]意味着，s1[i]和s2[j]中至少有一个字符不在lcs中

如上图，总共可能有三种情况，我怎么知道具体是那种情况呢？
其实我们也不知道，那就把这三种情况的答案都算出来，取其中结果最大的那个，因为题目让我们算「最长」公共子序列的长度。
所以推导逻辑
if (text1[i] != text2[j]) dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
这里已经做了一个小的优化，情况三「s1[i]和s2[j]都不在 lcs 中」其实可以直接忽略，因为情况三被情况一和情况二包含了。

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int len1 = text1.size();
        int len2 = text2.size();
        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];
    }
};

延伸题目

583. 两个字符串的删除操作

712. 两个字符串的最小ASCII删除和 （⭐）