使用动态规划来计算字串 python代码

动态规划是一种通过将复杂问题分解为更小的子问题并存储解决方案来优化计算过程的方法。在Python中，我们可以利用动态规划解决字符串相关的最优化问题，比如最长公共子序列（Longest Common Subsequence, LCS）或背包问题。

下面是一个简单的例子，展示了如何使用动态规划计算两个字符串的最长公共子序列：

def longest_common_subsequence(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n+1) for _ in range(m+1)]  # 初始化动态规划矩阵

    # 状态转移方程
    for i in range(1, m+1):
        for j in range(1, n+1):
            if s1[i-1] == s2[j-1]:  # 如果当前字符相同
                dp[i][j] = dp[i-1][j-1] + 1
            else:  # 如果不同
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])  # 选择上一列或上一行的较长路径

    # 最终结果在dp[m][n]
    return dp[m][n]

# 示例
s1 = "ABCDGH"
s2 = "AEDFHR"
lcs_length = longest_common_subsequence(s1, s2)
print(f"最长公共子序列的长度: {lcs_length}")

在这个例子中，`dp[i][j]`表示`s1`前i个字符和`s2`前j个字符的最长公共子序列的长度。动态规划数组由外到内填充，最后的结果就是我们需要的答案。