动态规划求解最长公共子序列（动态规划求解最长公共子序列问题有bug吗）

## 动态规划求解最长公共子序列

简介

最长公共子序列（Longest Common Subsequence，LCS）是一个经典的计算机科学问题，它旨在寻找两个序列中最长的子序列（不需要连续）。例如，"ABCD" 和 "AEBD" 的最长公共子序列是 "ABD"，长度为 3。动态规划是解决 LCS 问题的常用且高效的算法。本文将详细介绍如何使用动态规划求解 LCS 问题。### 1. 问题定义给定两个序列 `X = {x1, x2, ..., xm}` 和 `Y = {y1, y2, ..., yn}`，找到它们的最长公共子序列。子序列是指从原序列中删除一些元素（可以不删除）后剩余元素的序列，保持原有顺序。### 2. 动态规划思路动态规划的核心思想是将问题分解成更小的子问题，并存储子问题的解以避免重复计算。对于 LCS 问题，我们定义 `c[i, j]` 为 `Xi = {x1, x2, ..., xi}` 和 `Yj = {y1, y2, ..., yj}` 的最长公共子序列的长度。我们可以通过以下递推关系式计算 `c[i, j]`：

如果 `xi = yj`:

则 `c[i, j] = c[i-1, j-1] + 1`。这意味着当前元素匹配，LCS 长度增加 1。

如果 `xi != yj`:

则 `c[i, j] = max(c[i-1, j], c[i, j-1])`。这意味着当前元素不匹配，LCS 长度等于 `Xi-1` 和 `Yj` 的 LCS 长度，或者 `Xi` 和 `Yj-1` 的 LCS 长度中的较大值。### 3. 算法实现以下是使用 Python 实现动态规划求解 LCS 问题的代码：```python def lcs(X, Y):m = len(X)n = len(Y)# 初始化二维数组 cc = [[0]

(n + 1) for _ in range(m + 1)]# 动态规划计算 c[i, j]for i in range(1, m + 1):for j in range(1, n + 1):if X[i - 1] == Y[j - 1]:c[i][j] = c[i - 1][j - 1] + 1else:c[i][j] = max(c[i - 1][j], c[i][j - 1])# 返回最长公共子序列的长度return c[m][n]def print_lcs(c, X, Y, i, j):"""打印最长公共子序列"""if i == 0 or j == 0:returnif X[i-1] == Y[j-1]:print_lcs(c, X, Y, i-1, j-1)print(X[i-1], end="")elif c[i-1][j] > c[i][j-1]:print_lcs(c, X, Y, i-1, j)else:print_lcs(c, X, Y, i, j-1)# 示例用法 X = "ABCDGH" Y = "AEDFHR" m = len(X) n = len(Y) c = [[0]

(n + 1) for _ in range(m + 1)] # 注意初始化length = lcs(X, Y) print("最长公共子序列的长度:", length) print("最长公共子序列:", end=" ") print_lcs(c,X, Y, m, n) #打印LCSX = "AGGTAB" Y = "GXTXAYB" m = len(X) n = len(Y) c = [[0]

(n + 1) for _ in range(m + 1)] # 注意初始化length = lcs(X, Y) print("\n最长公共子序列的长度:", length) print("最长公共子序列:", end=" ") print_lcs(c,X, Y, m, n) #打印LCS```### 4. 复杂度分析

时间复杂度:

O(mn)，其中 m 和 n 分别是两个序列的长度。这是因为需要填充一个 m x n 的二维数组。

空间复杂度:

O(mn)，用于存储二维数组 `c`。### 5. 总结动态规划是解决 LCS 问题的有效方法。通过构建递推关系式和利用存储子问题解的思想，可以高效地计算两个序列的最长公共子序列的长度以及具体的子序列。理解动态规划的思想对于解决其他类似的优化问题也至关重要。

动态规划求解最长公共子序列**简介**最长公共子序列（Longest Common Subsequence，LCS）是一个经典的计算机科学问题，它旨在寻找两个序列中最长的子序列（不需要连续）。例如，"ABCD" 和 "AEBD" 的最长公共子序列是 "ABD"，长度为 3。动态规划是解决 LCS 问题的常用且高效的算法。本文将详细介绍如何使用动态规划求解 LCS 问题。

1. 问题定义给定两个序列 `X = {x1, x2, ..., xm}` 和 `Y = {y1, y2, ..., yn}`，找到它们的最长公共子序列。子序列是指从原序列中删除一些元素（可以不删除）后剩余元素的序列，保持原有顺序。

2. 动态规划思路动态规划的核心思想是将问题分解成更小的子问题，并存储子问题的解以避免重复计算。对于 LCS 问题，我们定义 `c[i, j]` 为 `Xi = {x1, x2, ..., xi}` 和 `Yj = {y1, y2, ..., yj}` 的最长公共子序列的长度。我们可以通过以下递推关系式计算 `c[i, j]`：* **如果 `xi = yj`:** 则 `c[i, j] = c[i-1, j-1] + 1`。这意味着当前元素匹配，LCS 长度增加 1。* **如果 `xi != yj`:** 则 `c[i, j] = max(c[i-1, j], c[i, j-1])`。这意味着当前元素不匹配，LCS 长度等于 `Xi-1` 和 `Yj` 的 LCS 长度，或者 `Xi` 和 `Yj-1` 的 LCS 长度中的较大值。

3. 算法实现以下是使用 Python 实现动态规划求解 LCS 问题的代码：```python def lcs(X, Y):m = len(X)n = len(Y)

初始化二维数组 cc = [[0] * (n + 1) for _ in range(m + 1)]

动态规划计算 c[i, j]for i in range(1, m + 1):for j in range(1, n + 1):if X[i - 1] == Y[j - 1]:c[i][j] = c[i - 1][j - 1] + 1else:c[i][j] = max(c[i - 1][j], c[i][j - 1])

返回最长公共子序列的长度return c[m][n]def print_lcs(c, X, Y, i, j):"""打印最长公共子序列"""if i == 0 or j == 0:returnif X[i-1] == Y[j-1]:print_lcs(c, X, Y, i-1, j-1)print(X[i-1], end="")elif c[i-1][j] > c[i][j-1]:print_lcs(c, X, Y, i-1, j)else:print_lcs(c, X, Y, i, j-1)

示例用法 X = "ABCDGH" Y = "AEDFHR" m = len(X) n = len(Y) c = [[0] * (n + 1) for _ in range(m + 1)]

注意初始化length = lcs(X, Y) print("最长公共子序列的长度:", length) print("最长公共子序列:", end=" ") print_lcs(c,X, Y, m, n)

打印LCSX = "AGGTAB" Y = "GXTXAYB" m = len(X) n = len(Y) c = [[0] * (n + 1) for _ in range(m + 1)]

注意初始化length = lcs(X, Y) print("\n最长公共子序列的长度:", length) print("最长公共子序列:", end=" ") print_lcs(c,X, Y, m, n)

打印LCS```

4. 复杂度分析* **时间复杂度:** O(mn)，其中 m 和 n 分别是两个序列的长度。这是因为需要填充一个 m x n 的二维数组。 * **空间复杂度:** O(mn)，用于存储二维数组 `c`。

5. 总结动态规划是解决 LCS 问题的有效方法。通过构建递推关系式和利用存储子问题解的思想，可以高效地计算两个序列的最长公共子序列的长度以及具体的子序列。理解动态规划的思想对于解决其他类似的优化问题也至关重要。