算法动态规划

最长公共子序列LCS，最经典的双串线性DP状态设计

字数统计: 1.2k字   |   阅读时长: 5分
, ,

摘要: 最长公共子序列，最长公共子串，动态规划解法。

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

本文我们看一下只要学动态规划就必然涉及的一题：最长公共子序列。它代表了双串上最经典的一类状态设计思路和阶段划分。

然后我们用类似的状态设计思路解决最长公共子串问题，对比跟最长公共子序列有什么区别。

最长公共子序列

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

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

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

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

提示：

1
2
1 <= text1.length, text2.length <= 1000
text1 和 text2 仅由小写英文字符组成。

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

示例 2：
输入：text1 = “abc”, text2 = “abc”
输出：3
解释：最长公共子序列是 “abc” ，它的长度为 3 。

示例 3：
输入：text1 = “abc”, text2 = “def”
输出：0
解释：两个字符串没有公共子序列，返回 0 。

算法：动态规划

LCS 是双串线性 DP 的基础问题，它的状态表示如下，共有 i,j 两个维度。

1
dp[i][j] := 考虑 s[0..i-1] 和 t[0..j-1] 时的最长公共子序列长度，

阶段划分为已经处理的前缀长度，也就是两个字符串中的位置，构成一个二维坐标。因此阶段已经足以表示状态，状态中没有附加信息维度。

其中 dp[0][j] 和 dp[i][0] 表示的是其中一个串一个字符也不考虑时的情况。

LCS 的这种状态表示和阶段划分方法在双串线性 DP 问题中很常见。

LCS

1
2
3
4
5
6
7
8
9
10
11
dp[i][j] := 考虑 s[0..i-1], t[0..j-1] 时，LCS 的长度

答案
dp[n][m]

初始化
dp[i][j] = 0

转移
dp[i][j] = dp[i - 1][j - 1] + 1             (s[i-1]==t[i-1])
         = max(dp[i][j - 1], dp[i - 1][j])  (s[i-1]!=t[i-1])

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int n = text1.size();
        int m = text2.size();
        vector<vector<int> > dp(n + 1, vector<int>(m + 1, 0));
        for(int i = 1; i < n + 1; ++i)
            for(int j = 1; j < m + 1; ++j)
            {
                if(text1[i - 1] == text2[j - 1])
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                else
                    dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
            }
        return dp[n][m];
    }
};

最长公共子串

给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。

示例 1：
输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
输出：3
解释：长度最长的公共子数组是 [3,2,1] 。

示例 2：
输入：nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
输出：5

提示：

1
2
1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 100

算法1: 动态规划

1
2
3
4
5
6
7
8
9
10
11
dp[i][j] := 考虑 A[i..] B[j..] 时，且分别以 A[i], B[j] 开头的最长公共前缀长度

答案
max(dp[i][j])

初始化
dp[i][j] := 0

转移
dp[i][j] = dp[i+1][j+1] + 1  (A[i]==B[j])
         = 0                 (A[i]!=B[j])

代码 (C++)

dp 开出 (n + 1) * (m + 1) 的空间，处理其中一串考虑另个字符的状态和相关的转移。这点与 LCS 的处理一样。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int findLength(vector<int>& A, vector<int>& B) {
        int na = A.size(), nb = B.size();
        vector<vector<int> > dp(na + 1, vector<int>(nb + 1, 0));
        int result = 0;
        for(int i = na - 1; i >= 0; --i)
            for(int j = nb - 1; j >= 0; --j)
            {
                if(A[i] == B[j])
                {
                    dp[i][j] = dp[i + 1][j + 1] + 1;
                    result = max(result, dp[i][j]);
                }
            }
        return result;
    }
};

算法2：值域二分 + 字符串哈希

参考文章 用字符串哈希解决经典问题：最长重复子串、最长公共子串。

Share