动态规划-最长公共子序列

题目

最长公共子序列
给定两个字符串 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 输入的字符串只含有小写英文字符。

思路

状态表示

我们可以使用动态规划（Dynamic Programming, DP）来解决这个问题。具体来说，我们使用一个二维数组 dp[i][j] 来表示 text1[0..i-1] 和 text2[0..j-1] 的最长公共子序列的长度。

dp[i][j] 表示 text1 的前 i 个字符与 text2 的前 j 个字符的最长公共子序列的长度。

状态计算

dp
在这里插入图片描述
\

四种情况分析

让我们详细分析这四种情况，以及它们如何影响 dp[i][j] 的值：

1. `00`（不包含 `text1[i-1]` 和 `text2[j-1]`）

这意味着我们在计算 dp[i][j] 时既不包含 text1[i-1] 也不包含 text2[j-1]，即我们从 dp[i-1][j-1] 继承。

但这里需要注意的是，这种情况实际上是“隐式”包含在下面两种情况中的，因此我们不需要单独列出：

情况 1: 如果 text1[i-1] != text2[j-1]，则最长公共子序列不会包括 text1[i-1] 或 text2[j-1]，我们需要从两个方向选择一个较大的值，表示我们“跳过”了这两个字符，即 dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

2. `01`（不包含 `text1[i-1]`，包含 `text2[j-1]`）

情况 2: 如果我们不考虑 text1[i-1]，但考虑 text2[j-1]，则 dp[i][j] = dp[i][j-1]，即我们不包括 text1[i-1]，但可能从 dp[i][j-1] 中获得结果。

3. `10`（包含 `text1[i-1]`，不包含 `text2[j-1]`）

情况 3: 如果我们不考虑 text2[j-1]，但考虑 text1[i-1]，则 dp[i][j] = dp[i-1][j]，即我们不包括 text2[j-1]，但可能从 dp[i-1][j] 中获得结果。

4. `11`（包含 `text1[i-1]` 和 `text2[j-1]`）

情况 4: 如果 text1[i-1] == text2[j-1]，那么我们可以同时包含 text1[i-1] 和 text2[j-1]，此时 dp[i][j] = dp[i-1][j-1] + 1。

合并这些情况

综合这些情况，我们可以得出状态转移方程：

如果 text1[i-1] == text2[j-1]，则：
$d p [i] [j] = d p [i - 1] [j - 1] + 1$
如果 text1[i-1] != text2[j-1]，则：
$\max(dp[i-1][j], dp[i][j-1])$

状态转移的总结

我们不需要显式地处理 00 这种情况，因为它已经包含在 01 和 10 中。当字符不相等时，我们从 dp[i-1][j] 和 dp[i][j-1] 中选取最大值，表示我们跳过了某个字符。

例子

考虑以下示例，text1 = "abcde" 和 text2 = "ace"：

	a	c	e
“”	0	0	0
a	1	1	1
b	1	1	1
c	1	2	2
d	1	2	2
e	1	2	3

dp[1][1] = 1，表示 "a" 和 "a" 匹配，公共子序列长度为 1。
dp[2][2] = 1，表示 "b" 和 "c" 不匹配，最长公共子序列仍然是之前的 "a"。
dp[3][3] = 2，表示 "c" 和 "e" 匹配，公共子序列变为 "ac"。
最终的 dp[5][3] = 3，表示 "abcde" 和 "ace" 的最长公共子序列长度为 3，子序列为 "ace"。

DP 数组的初始化

DP 数组 dp[i][j] 的定义是：dp[i][j] 表示 text1[0..i-1] 和 text2[0..j-1] 的最长公共子序列的长度。

初始化步骤

当 text1 或 text2 中有一个字符串为空时，显然其与另一个字符串的公共子序列的长度为 0。因此，所有的 dp[0][j] 和 dp[i][0] 都应该初始化为 0。
- dp[0][j] = 0，表示当 text1 为空时，任何 text2 子串的最长公共子序列长度为 0。
- dp[i][0] = 0，表示当 text2 为空时，任何 text1 子串的最长公共子序列长度为 0。
一般情况下，初始化二维 DP 数组的过程如下：
- 创建一个大小为 (m+1) x (n+1) 的二维数组，其中 m 是 text1 的长度，n 是 text2 的长度。
- 初始化 dp[0][j] 和 dp[i][0] 为 0。

代码实现

def longestCommonSubsequence(text1: str, text2: str) -> int:m, n = len(text1), len(text2)# 初始化 DP 数组，大小为 (m+1) x (n+1)dp = [[0] * (n + 1) for _ in range(m + 1)]# 填充 DP 数组for i in range(1, m + 1):for j in range(1, n + 1):if text1[i - 1] == text2[j - 1]:# 如果字符相等，当前公共子序列的长度加1dp[i][j] = dp[i - 1][j - 1] + 1else:# 如果字符不等，取最大值，表示跳过当前字符dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])# 返回最终的结果return dp[m][n]

代码解析

初始化 DP 数组：
- 使用 dp = [[0] * (n + 1) for _ in range(m + 1)] 初始化了一个大小为 (m+1) x (n+1) 的二维数组，dp[i][j] 用来存储 text1[0..i-1] 和 text2[0..j-1] 的最长公共子序列长度。
- 初始化时，dp[i][0] 和 dp[0][j] 都被设置为 0，表示当任意一个字符串为空时，最长公共子序列的长度为 0。
DP 填充过程：
- 对于每一对字符 text1[i-1] 和 text2[j-1]，如果字符相等，那么 dp[i][j] = dp[i-1][j-1] + 1。
- 如果字符不等，dp[i][j] = max(dp[i-1][j], dp[i][j-1])，表示我们要么跳过 text1[i-1]，要么跳过 text2[j-1]。
返回结果：
- 最终的最长公共子序列的长度存储在 dp[m][n] 中，即 text1[0..m-1] 和 text2[0..n-1] 的最长公共子序列长度。

时间和空间复杂度

时间复杂度：O(m * n)，我们需要遍历 text1 和 text2 的每一对字符，并更新 DP 表。
空间复杂度：O(m * n)，我们使用了一个二维数组来存储所有子问题的解。

空间优化

如果只关心当前行和上一行的状态，我们可以优化空间复杂度，使用滚动数组（两个一维数组）代替二维数组，减少空间消耗。

def longestCommonSubsequence(text1: str, text2: str) -> int:m, n = len(text1), len(text2)# 初始化两个一维数组，分别用于存储上一行和当前行prev = [0] * (n + 1)curr = [0] * (n + 1)# 填充 DP 数组for i in range(1, m + 1):for j in range(1, n + 1):if text1[i - 1] == text2[j - 1]:curr[j] = prev[j - 1] + 1else:curr[j] = max(prev[j], curr[j - 1])# 将当前行的结果存入上一行，准备计算下一行prev, curr = curr, prev# 返回最终结果return prev[n]

好的！下面我将为你提供 Go 和 C++ 语言的代码实现，帮助你在这两种语言中解决 最长公共子序列（LCS）问题。

Go 语言实现

package mainimport "fmt"func longestCommonSubsequence(text1 string, text2 string) int {m, n := len(text1), len(text2)// 初始化一个二维数组 dp，用于存储子问题的结果dp := make([][]int, m+1)for i := range dp {dp[i] = make([]int, n+1)}// 填充 dp 数组for i := 1; i <= m; i++ {for j := 1; j <= n; j++ {if text1[i-1] == text2[j-1] {dp[i][j] = dp[i-1][j-1] + 1  // 如果字符相等，公共子序列长度增加} else {dp[i][j] = max(dp[i-1][j], dp[i][j-1])  // 否则取最大值}}}// 返回最终的结果，dp[m][n] 就是最长公共子序列的长度return dp[m][n]
}// 辅助函数：返回两个整数中的较大者
func max(a, b int) int {if a > b {return a}return b
}func main() {text1 := "abcde"text2 := "ace"fmt.Println(longestCommonSubsequence(text1, text2))  // 输出 3
}

C++ 语言实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;int longestCommonSubsequence(string text1, string text2) {int m = text1.size(), n = text2.size();// 创建一个 (m+1) x (n+1) 的二维 dp 数组vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));// 填充 dp 数组for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (text1[i - 1] == text2[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;  // 如果字符相等，公共子序列长度加 1} else {dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);  // 否则取最大值}}}// 返回最长公共子序列的长度return dp[m][n];
}int main() {string text1 = "abcde";string text2 = "ace";cout << longestCommonSubsequence(text1, text2) << endl;  // 输出 3return 0;
}

代码解释

初始化 DP 数组：
在这两个实现中，我们都创建了一个二维数组 dp，dp[i][j] 表示 text1[0..i-1] 和 text2[0..j-1] 的最长公共子序列的长度。数组的尺寸为 (m+1) x (n+1)，m 和 n 分别是两个字符串的长度。dp[i][0] 和 dp[0][j] 都初始化为 0，表示当某个字符串为空时，最长公共子序列的长度为 0。
填充 DP 表：
- 我们遍历每一对字符 text1[i-1] 和 text2[j-1]，如果这两个字符相等，那么公共子序列的长度是 dp[i-1][j-1] + 1，否则取 dp[i-1][j] 和 dp[i][j-1] 的最大值，表示我们跳过了其中一个字符。
返回结果：
最终，dp[m][n] 存储的就是 text1 和 text2 的最长公共子序列的长度。

Go 语言优化版：

package mainimport "fmt"func longestCommonSubsequence(text1 string, text2 string) int {m, n := len(text1), len(text2)// 保留上一行和当前行的数组prev := make([]int, n+1)curr := make([]int, n+1)// 填充 DP 数组for i := 1; i <= m; i++ {for j := 1; j <= n; j++ {if text1[i-1] == text2[j-1] {curr[j] = prev[j-1] + 1} else {curr[j] = max(prev[j], curr[j-1])}}prev, curr = curr, prev  // 切换当前行和上一行}return prev[n]  // 返回结果
}func max(a, b int) int {if a > b {return a}return b
}func main() {text1 := "abcde"text2 := "ace"fmt.Println(longestCommonSubsequence(text1, text2))  // 输出 3
}

C++ 语言优化版：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;int longestCommonSubsequence(string text1, string text2) {int m = text1.size(), n = text2.size();// 初始化两行数组vector<int> prev(n + 1, 0), curr(n + 1, 0);// 填充 DP 数组for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (text1[i - 1] == text2[j - 1]) {curr[j] = prev[j - 1] + 1;} else {curr[j] = max(prev[j], curr[j - 1]);}}prev = curr;  // 切换当前行和上一行}return prev[n];  // 返回结果
}int main() {string text1 = "abcde";string text2 = "ace";cout << longestCommonSubsequence(text1, text2) << endl;  // 输出 3return 0;
}