经典DP问题——最长公共子序列

Leetcode刷题
留言

典中典的动态规划

1143 最长公共子序列

题目描述

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

一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

  • 例如，”ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。

两个字符串的公共子序列是这两个字符串所共同拥有的子序列。

示例 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, text2.length <= 1000$
  • text1 和 text2 仅由小写英文字符组成。

解法——动态规划

拿到这道题如果没有意识到动态规划，就会感觉似乎是一个NP问题，但事实上这是一道十分经典的二维动态规划问题。动态规划问题的特征就是我们可以将问题进行拆分，然后可以通过定义问题状态和状态之间的关系，使得问题可以以递推的方式来解决。

两个字符串找最大公共子串，其实就可以先转换为一个字符串和另一个不断增长的字符串找公共子串，再进一步转换为两个不断增长的字符串找公共子串。

我们假设两个字符串$test1，test2$长度为m、n，我们创建一个$m+1$行$n+1$列的二维数组$dp$，而$dp[i][j]$表示的就是第一个字符串从第0个字符到第$i-1$个字符所组成的字符串和第二个字符串从第0个字符到第$j-1$个字符所组成的字符串的最大公共子串的长度。换句话说就是两个字符串长度为$i，j$的前缀字符串的最大公共子串。

然后对于$dp$数组的边界情况：显然无论$i==0j==0$,他们的最大公共子串都为0。因此$dp$数组的第0行和第0列的所有值必然都为0。也即当$i==0||j==0$时，$dp[i][j]=0$.

当$i>0||j>0$时，对$dp$数组进行计算：

  • 如果$test1[i-1]=test2[j-1]$,那么这两个字符就是公共字符，这说明我们可以把前缀字符串中的最大公共字符串长度+1了，所以$dp[i][j]=dp[i-1][j-1]+1$。为什么这里时$i-1$和$j-1$呢，因为这里的$i$和$j$并不是代表字符串数组下标，而是代表$dp$数组的下标，$dp$数组为了考虑字符串长度为0的情况是有单独一行一列下标，所以$dp$数组的下标要比真实的字符串的下标大1
  • 如果$test1[i-1]!=test2[j-1]$，那么这两个字符串就不是公共字符，那么显然对于$dp[i][j]$而言，它的取址就应该是前一个状态的取址，所以就要看$dp[i-1]$[j]和$dp[i][j-1]$的取值，较大的就是$dp[i][j]$的取值

综上所述，我们可以得到状态转移方程：

                                                                    $$dp[i][j]=\left\{\begin{aligned}dp[i-1][j-1]+1,text1[i]==text2[j]\\max(dp[i-1][j],dp[i][j-1]),text1[i]!=text2[j]\end{aligned}\right.$$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.size(), n = text2.size();
        vector<vector<int>> dp(m+1,vector<int>(n+1));

        for(int i=1;i<=m;i++){
            char c1 = text1[i-1];
            for(int j=1;j<=n;j++){
                char c2 = text2[j-1];
                if(c1==c2){
                    dp[i][j] = dp[i-1][j-1]+1;
                }else{
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return dp[m][n];
    }
};

复杂度分析

  • 时间复杂度：$O(m\times n)$，其中m和n分别是字符串$text1$,$text2$ 的长。我们根据m和n遍历了长宽为$m+1$ $n+1$的$dp$数组
  • 空间复杂度：$O(m\times n)$，其中m和n分别是字符串$text1$,$text2$ 的长。我们根据m和n建立了长宽为$m+1$ $n+1$的$dp$数组