通过python用动态规划实现最长公共子序列

最长公共子序列（Longest Common Subsequence, LCS）是指给定两个字符串，找到这两个字符串中都存在的最长的子序列。

动态规划是解决LCS问题的一种常用方法。具体实现是先创建一个二维数组，横轴表示字符串1，纵轴表示字符串2，数组中每个位置存储的值表示当前位置为止两个字符串的公共子序列的长度。然后从左上角开始，一行一行的填充数组，填充的过程中需要根据两个字符串当前位置的字符是否相等来判断数组位置上的值。最后返回数组右下角的值即为LCS的长度。

下面是Python实现的代码示例：

def lcs(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]

这个函数的输入是两个字符串，输出是它们的最长公共子序列的长度。