一、题目描述

给定两个字符串 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

输入的字符串只含有小写英文字符。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/longest-common-subsequence

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、思路

参考大神思路解析：https://leetcode-cn.com/problems/longest-common-subsequence/solution/dong-tai-gui-hua-tu-wen-jie-xi-by-yijiaoqian/

审题

最长公共子序列（Longest Common Subsequence，简称 LCS）是一道非常经典的面试题目，因为它的解法是典型的二维动态规划，大部分比较困难的字符串问题都和这个问题一个套路，比如说编辑距离。而且，这个算法稍加改造就可以用于解决其他问题，所以说 LCS 算法是值得掌握的。

所谓子序列，就是要保留原始顺序，但可以是不连续的。审题之后你可能会有疑问，这个问题为啥就是动态规划来解决呢？因为子序列类型的问题，穷举出所有可能的结果都不容易，而动态规划算法做的就是穷举 + 剪枝，它俩天生一对儿。所以可以说只要涉及子序列问题，十有八九都需要动态规划来解决。

动态规划思路

第一步，一定要明确 dp 数组的含义。

对于两个字符串的动态规划问题，套路是通用的。

比如说对于字符串 s1 和 s2，它们的长度分别是 m、n，一般来说都要构造一个这样的 DP table：int[][] dp = new int[m+1][n+1]。

这里为什么要加 1，原因是你可以不加 1，但是不加 1 你就会用其它限制条件来确保这个 index 是有效的，而当你加 1 之后你就不需要去判断只是让索引为 0 的行和列表示空串。

第二步，定义 base case

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

第三部，找状态转移方程

这是动态规划最难的一步，我们来通过案例推导出来。

对于 text1：abcde 和 text2：ace 两个字符串，我们定义两个指针进行遍历 i 和 j。

遍历 text1 长度为 m，定义指针 i，从 0～m。固定 i 指针（i == 1）位置，接下来开始遍历 text2 长度为 n，定义指针 j，从 0~n。

第一次遍历 i = 1, j = 1，两个 a 相同所以 dp[1][1] = 1

第二次遍历 i = 1, j = 2，a 与 c 不等，也不能是 0，这里需转换成 a 与 ac 最长子序列，这里需要把之前的关系传递过来，所以 dp[1][2] = 1

第三次遍历 i = 1, j = 3，a 与 e 不相同，把之前的关系传递过来，所以 dp[1][3] = 1

text2：ace 已经走完来第一轮，接下来 text1：abcde 走到来 b 字符。

第四次遍历 i = 2, j = 1，就是需要比较 ab 与 a 的最长子串，把之前的关系传递过来，所以 dp[2][1] = 1

依次类推...（详看上图）

我们会发现遍历两个串字符，当不同时需要考虑两层遍历前面的值（关系传递），也就是左边和上边的其中较大的值，当想相同时，需要考虑各自不包含当前字符串的子序列长度，再加上 1。

因此可以得出：

现在对比的这两个字符不相同的，那么我们要取它的「要么是 text1 往前退一格，要么是 text2 往前退一格，两个的最大值」

dp[i + 1][j + 1] = Math.max(dp[i+1][j], dp[i][j+1]);

对比的两个字符相同，去找它们前面各退一格的值加 1 即可：dp[i+1][j+1] = dp[i][j] + 1;

三、代码实现

// javaclass Solution {    public int longestCommonSubsequence(String text1, String text2) {        int m = text1.length(), n = text2.length();        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i < m; i++) {            for (int j = 0; j < n; j++) {                // 获取两个串字符                char c1 = text1.charAt(i), c2 = text2.charAt(j);                if (c1 == c2) {                    // 去找它们前面各退一格的值加1即可                    dp[i + 1][j + 1] = dp[i][j] + 1;                } else {                    //要么是text1往前退一格，要么是text2往前退一格，两个的最大值                    dp[i + 1][j + 1] = Math.max(dp[i + 1][j], dp[i][j + 1]);                }            }        }        return dp[m][n];    }}

四、小结

DP 动态规划题目在于推导转移状态数组，感觉路很长，也是很多人不会的原因。这点需要加强