【实验二最长公共子序列(动态规划算法)（doc）】一、实验目的
本实验旨在通过动态规划算法，实现对两个字符串的最长公共子序列（Longest Common Subsequence, LCS）问题的求解。通过该实验，学生应掌握动态规划的基本思想与实现方法，并理解其在实际问题中的应用价值。
二、实验原理
最长公共子序列问题是经典的动态规划问题之一。所谓“子序列”，是指从原序列中按顺序删除若干字符后得到的新序列，不一定是连续的。而“最长公共子序列”则是指两个给定字符串中都存在的最长的子序列。
例如，对于字符串 `X = "ABCBDAB"` 和 `Y = "BDCAB"`，它们的最长公共子序列是 `"BCAB"` 或 `"BDAB"`，长度为4。
动态规划的核心思想是将大问题分解为多个小问题，并存储中间结果以避免重复计算。对于LCS问题，我们定义一个二维数组 `dp[i][j]`，表示字符串 `X[0..i-1]` 与 `Y[0..j-1]` 的最长公共子序列长度。状态转移方程如下：
- 如果 `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])`
三、实验步骤
1. 输入两个字符串：用户输入两个字符串 `X` 和 `Y`。
2. 初始化动态规划表：创建一个 `(len(X)+1) × (len(Y)+1)` 的二维数组 `dp`，初始值全部为0。
3. 填充动态规划表：根据状态转移方程，逐行逐列填充 `dp` 数组。
4. 输出结果：最终 `dp[len(X)][len(Y)]` 即为最长公共子序列的长度。
5. 回溯路径（可选）：若需要找出具体的公共子序列，可以通过回溯 `dp` 表来构造。
四、代码实现（Python 示例）
```python
def lcs(X, Y):
m = len(X)
n = len(Y)
创建一个 (m+1) x (n+1) 的二维数组
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 = "BDCAB"
print("最长公共子序列长度为:", lcs(X, Y))
```
五、实验结果与分析
运行上述代码后，可以得到两个字符串的最长公共子序列长度。例如，当 `X = "ABCBDAB"` 与 `Y = "BDCAB"` 时，程序输出结果为 `4`，说明两者存在长度为4的公共子序列。
此外，通过修改代码添加回溯逻辑，还可以进一步输出具体的公共子序列内容，帮助更直观地理解算法过程。
六、实验总结
通过本次实验，掌握了动态规划算法在解决LCS问题中的应用，理解了如何构建状态转移方程以及如何优化时间复杂度和空间复杂度。同时，也认识到动态规划在处理具有重叠子问题和最优子结构的问题时的强大优势。
七、思考与拓展
- 可以尝试使用一维数组优化空间复杂度。
- 尝试将算法应用于其他实际场景，如文本比对、基因序列分析等。
- 探索不同算法（如递归、记忆化搜索）与动态规划的效率对比。
