如何用Python实现 longest common subsequence (LCS) 的动态规划算法？

在Python中，可以使用动态规划方法来解决最长公共子序列（Longest Common Subsequence，LCS）问题。下面是基本的步骤：

1. 定义问题：给定两个字符串 `str1` 和 `str2`，找到它们共享的最长子序列的长度。

2. 创建动态规划矩阵：创建一个二维数组 `dp`，其中 `dp[i][j]` 表示 `str1` 的前 `i` 个字符和 `str2` 的前 `j` 个字符之间的最长公共子序列的长度。

3. 初始化矩阵：如果 `i=0` 或者 `j=0`，则它们的最长公共子序列就是它们自身，所以 `dp[i][j] = 0`。

4. 动态填充矩阵：对于 `dp[i][j]`（`i>0`, `j>0`），有两种情况：
- 如果 `str1[i-1] == str2[j-1]`，说明当前字符匹配，最长公共子序列长度加一，即 `dp[i][j] = dp[i-1][j-1] + 1`。
- 否则，即 `str1[i-1] != str2[j-1]`，我们选择不包含当前字符的最长公共子序列，取 `dp[i-1][j]` 和 `dp[i][j-1]` 中的最大值，即 `dp[i][j] = max(dp[i-1][j], dp[i][j-1])`。

5. 最终结果：当遍历完整个矩阵后，`dp[len(str1)][len(str2)]` 就是所求的最长公共子序列的长度。

以下是 Python 代码实现的例子：

def lcs_length(str1, str2):
    m, n = len(str1), len(str2)
    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 = "ABCDGH"
str2 = "AEDFHR"
print("Length of LCS is:", lcs_length(str1, str2))