题目

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

若这两个字符串没有公共子序列，则返回 0。
在这里插入图片描述
提示:

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

解题思路

只要涉及到子序列问题，十有八九是用动态规划解决。所以下面来进行动态规划三步骤：
1、确定dp数组的含义：
对于两个字符串的动态规划问题，套路都差不多。需要定义一个二维的dp数组。其中dp[i][j]的含义是：对于字符串str1[0...i-1]和str2[0...j-1]，它们的LCS（最长公共子序列）长度是dp[i][j]。

你可能会有疑问，str1、2不应该是到str1[0…i]么，为啥只到了i-1? 下面来举个例子看一下。
在这里插入图片描述
有没有发现，在这个DP表中。每个字符串的下标0位置，都被一个空串给占了（这样做是为了方便初始化dp，也就是方便处理base case ）。所以啊，这也很好的解释了为啥我们定义dp数组的长度的时候，要用字符串的长度+1。因为多出来的一个位置就是给这个空串的。

比如嘛dp[2][4]=2，的含义就是对于"ac"和"babc"的LCS长度是2。

最重要的就是理解，在DP表中空串占了下标0的位置，但是对于字符串来说，下标还是按照原来的，即我dp[2][2] ，对应的其实是字符串str1[1]和str2[1]

2、定义base case

专门让dp表中索引为 0 的行和列表示空串，dp[0][..]和 dp[..][0]都应该初始化为 0，这就是 base case。

比如说，按照刚才 dp 数组的定义，dp[0][3]=0 的含义是：对于字符串 " " 和 "bab"，其 LCS 的长度为 0。因为有一个字符串是空串，它们的最长公共子序列的长度显然应该是 0。

3、找到状态转移方程
状态转移说简单些就是做选择，找到有哪些状态，再在这些状态中做选择。

这个问题，是求 s1 和 s2 的最长公共子序列，不妨称这个子序列为 lcs。那么对于 s1 和 s2 中的每个字符，有什么选择？很简单，两种选择，要么在 lcs 中，要么不在。
在这里插入图片描述

如果某个字符应该在 lcs 中，那么这个字符肯定同时存在于 s1 和 s2 中

所以本题的思路是这样：

从后往前遍历 s1 和 s2，如果 s1[i]==s2[j]，那么这个字符一定在 lcs 中；
否则的话，s1[i] 和 s2[j] 这两个字符至少有一个不在 lcs 中，需要丢弃一个。

代码

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();


        int[][] dp = new int[m + 1][n + 1];

        for (int i = 1; i <= m; i++) {//i可以等于m，是因为dp的长度为m+1，所以下标m对应着dp的最后一个元素
            for (int j = 1; j <= n; j++) {//j可以等于n，理由同上
                //charAt(i - 1),即字符串的第i个字符，便利的时候下标要比长度小1
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {//如果str1的第i个字符和str2的第j个字符相等
                    dp[i][j] = dp[i - 1][j - 1] + 1;

                } else {
                //谁能让 lcs 最长，就听谁的
                    dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
                }

            }

        }

        return dp[m][n];
    }
}