1143.最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

输入：text1 = "abcde", text2 = "ace" 输出：3
解释：最长公共子序列是 "ace" ，它的长度为 3 。

1.一刷动规

一般来讲题目问什么动态规划的dp数组的含义就定什么，多为长度。这道题里dp[i][j]表示text1前i个字符串和text2前j个字符串的最长公共子序列的长度。分两种情况：

• text1.charAt(i)不等于text2.charAt(j)时，dp[i][j]=Math.max(dp[i][j-1]，dp[i-1][j]，dp[i-1][j-1])，其中dp[i-1][j]表明当前text1[i]不参与构成最长公共子序列。
• text1.charAt(i)等于text2.charAt(j)时，dp[i][j]=dp[i-1][j-1]+1，把当前text1[i]纳入最长公共子序列。这种写法其实按照公共子序列右对齐的形式。

2.二刷+长度继承思想

分析：本题重点在于理解二维dp[i][j]的长度继承思想，也就是说即使text1[i]不等于text2[j]，那么也需要把text1[0,i]与text2[0,j]前面两段已经顺序匹配的字符串长度继承下来。而为什么可以继承？因为题目要求的子序列不要求是连续的。更新时需要根据前面三个方向的值进行状态转换：

事实上如果dp保存的不是长度，而是保存判断字符text1[i]是否等于text2[j]一个标识，那么每次相等时都需要遍历统计dp[0 ~ i-1][0 - j-1]范围内等于1的个数，结果作为以当前字符结尾的最长子序列长度。最坏情况下时间复杂度为O(m方n方)

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int[][] dp=new int[text1.length()][text2.length()];
        int res=0;
        for(int i=0;i<text1.length();i++){
            for(int j=0;j<text2.length();j++){
                if(i-1>=0) dp[i][j]=Math.max(dp[i][j],dp[i-1][j]);
                if(j-1>=0) dp[i][j]=Math.max(dp[i][j],dp[i][j-1]);
                
                if(text1.charAt(i)==text2.charAt(j)){
                    if(i-1>=0&&j-1>=0) dp[i][j]=Math.max(dp[i][j],dp[i-1][j-1]+1);
                    else dp[i][j]=Math.max(dp[i][j],1);
                }
                res=Math.max(res,dp[i][j]);
            }
        }
        return res;
    }
}

3.相似变种题目

1035. 不相交的线 (opens new window)

线只要不相交，那么说明两个模板选择的数都满足“子序列”的顺序性。

583. 两个字符串的删除操作 (opens new window)

• 问题等价于找到LCS，两个字符串相互匹配的LCS可以保留作为最终匹配串。剩余的字符串可以删掉。
• 定义dp表示以第i个字符串结尾和第j个字符串结尾的两个字符串，变成相同字符串所需要的最小步数：

class Solution {
    public int minDistance(String word1, String word2) {
        int[][] dp=new int[word1.length()+1][word2.length()+1];
        int res=0;
        for(int i=1;i<=word1.length();i++) dp[i][0]=dp[i-1][0]+1;
        for(int i=1;i<=word2.length();i++) dp[0][i]=dp[0][i-1]+1;
        for(int i=1;i<=word1.length();i++){
            for(int j=1;j<=word2.length();j++){
                dp[i][j]=Math.min(dp[i][j-1],dp[i-1][j])+1;
                if(word1.charAt(i-1)==word2.charAt(j-1)) dp[i][j]=Math.min(dp[i][j],dp[i-1][j-1]);
            }
        }
        return dp[word1.length()][word2.length()];

    }
}