1143. 最长公共子序列（动态规划）

左手的ㄟ右手 2023-10-05 18:48 13阅读 0赞

#### 1143. 最长公共子序列 ####

*  题目
 *  解题思路
 *  代码

## 题目 ##

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

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

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

*  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?** 下面来举个例子看一下。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70 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 中，要么不在。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70 2]

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

所以本题的思路是这样：

1.  从后往前遍历 s1 和 s2，如果 s1\[i\]==s2\[j\]，那么这个字符一定在 lcs 中；
2.  否则的话，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];
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/202101302105407.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/2021013021121644.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/2021013021324254.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5,size_16,color_FFFFFF,t_70