代码随想录算法训练营第60天｜84

**代码随想录算法训练营第60天**

**84. 最长公共子序列(LCS)**今天，我们要讨论一个经典的动态规划问题：最长公共子序列（LCS）。这个问题是这样的：给定两个字符串 `X` 和 `Y`，我们需要找到这两个字符串之间的最长公共子序列。

**什么是最长公共子序列？**

最长公共子序列是指两个字符串中共同出现的最大子序列。例如，如果两个字符串分别是 `"ABCD"` 和 `"CBED"`,那么它们的最长公共子序列是 `"CBE"`。

**动态规划解决方案**

我们可以使用动态规划来解决这个问题。动态规划是一种通过分解大问题为小问题并求解这些小问题来解决大问题的方法。

首先，我们需要定义一个二维数组 `dp`，其中 `dp[i][j]` 表示第 `i` 个字符和第 `j` 个字符之间的最长公共子序列的长度。

我们可以通过以下公式计算 `dp[i][j]`：

* 如果 `X[i-1] == Y[j-1]`,那么 `dp[i][j] = dp[i-1][j-1] +1`
* 否则，`dp[i][j] = max(dp[i-1][j], dp[i][j-1])`

这里，我们使用了一个很重要的观察：如果两个字符相同，那么它们之间的最长公共子序列就是前面两个字符之间的最长公共子序列加上这个新字符。

我们可以通过递归地计算 `dp` 来求解这个问题。但是，这个方法会导致重复计算很多次。因此，我们需要使用动态规划来避免这种情况。

**代码示例**

def lcs(X, Y):
 m = len(X)
 n = len(Y)

 # 初始化 dp 数组 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 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 = "ABCD"
Y = "CBED"

print(lcs(X, Y)) # 输出:3