LCS 问题：最长公共子序列

最长公共子序列（Longest Common Subsequence，LCS）问题是计算机科学中一个经典的动态规划问题。给定两个序列，找出它们的最长公共子序列。

LCS 问题示例

假设我们有两个字符串：

A = "AGGTAB"
B = "GXTXAYB"

它们的最长公共子序列为：

"GTAB"

动态规划解法

LCS 问题的动态规划解法主要基于以下思想：

1. 构建一个二维数组 dp，其中 dp[i][j] 表示 A 的前 i 个字符和 B 的前 j 个字符的最长公共子序列的长度。
2. 初始化 dp[0][j] 和 dp[i][0] 为 0，因为空字符串和任何字符串的最长公共子序列长度都是 0。
3. 遍历 A 和 B 的所有字符，根据以下规则填充 dp 数组：
   • 如果 A[i-1] == B[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1；
   • 否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

代码示例

以下是一个 Python 代码示例，实现了 LCS 问题的动态规划解法：

def lcs(A, B):
    m, n = len(A), len(B)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if A[i - 1] == B[j - 1]:
                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]

A = "AGGTAB"
B = "GXTXAYB"
print(lcs(A, B))

扩展阅读

如果您想了解更多关于 LCS 问题的动态规划解法，可以阅读以下文章：

• 最长公共子序列算法详解
• 动态规划入门指南

```html
<center><img src="https://cloud-image.ullrai.com/q/dynamic_programming/" alt="Dynamic Programming"/></center>