最长公共子序列的动态规划算法
时间: 2023-07-08 08:16:05 浏览: 45
最长公共子序列(Longest Common Subsequence,LCS)的动态规划算法可以通过以下步骤实现:
1.定义状态:设 $dp[i][j]$ 表示序列 $A$ 的前 $i$ 个元素与序列 $B$ 的前 $j$ 个元素的 LCS 长度。
2.初始化:$dp[i][0]=0$ 和 $dp[0][j]=0$,即两个序列中有一个为空时,LCS 长度为0。
3.状态转移方程:当 $A_i=B_j$ 时,$dp[i][j]=dp[i-1][j-1]+1$,表示当前元素可以加入 LCS 中;当 $A_i\neq B_j$ 时,$dp[i][j]=\max(dp[i-1][j],dp[i][j-1])$,表示当前元素不能同时加入 LCS 中,需要在序列 $A$ 的前 $i-1$ 个元素和序列 $B$ 的前 $j$ 个元素的 LCS 和序列 $A$ 的前 $i$ 个元素和序列 $B$ 的前 $j-1$ 个元素的 LCS 中取较大值。
4.最终结果:$dp[m][n]$ 表示序列 $A$ 和序列 $B$ 的 LCS 长度,其中 $m$ 和 $n$ 分别为两个序列的长度。
下面是一个基于动态规划的 Python 代码实现:
```python
def lcs(str1, str2):
m, n = len(str1), len(str2)
# 初始化 dp 数组
dp = [[0] * (n + 1) for _ in range(m + 1)]
# 动态规划求解
for i in range(1, m + 1):
for j in range(1, n + 1):
if str1[i - 1] == str2[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]
```
其中, `str1` 和 `str2` 分别为两个输入序列。