动态规划 最长公共子序列

最长公共子序列（Longest Common Subsequence，LCS）是指对于两个序列 X 和 Y，找出它们的最长公共子序列。

动态规划解法：

1. 定义状态：设 X 和 Y 分别为长度为 m 和 n 的序列，LCS(i, j) 表示 X 的前 i 个字符和 Y 的前 j 个字符的最长公共子序列长度。

2. 状态转移方程：

如果 X[i] == Y[j]，则 LCS(i, j) = LCS(i-1, j-1) + 1；

否则，LCS(i, j) = max(LCS(i-1, j), LCS(i, j-1))。

3. 初始化：LCS(i, 0) 和 LCS(0, j) 都为 0。

4. 最终结果：LCS(m, n)。

Python 代码实现：

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

例如：

X = "ABCBDAB"
Y = "BDCABA"
print(lcs(X, Y)) # 输出 4，即 BCBA。