Python 中简单的动态规划问题解决方法

动态规划（Dynamic Programming）是一种分阶段求解决策问题的数学思想，其基本思路是将复杂的问题分解为简单的子问题（最优子结构），通过保存子问题的解来避免重复计算（重叠子问题），从而得到原问题的最优解。在Python中，可以通过递归或者循环的方式来实现动态规划。

例如，求解最长公共子序列问题（Longest Common Subsequence，LCS），可以使用递归的方式，先考虑最简单的情况，即当两个字符串长度均为1时，LCS的长度为0或1，然后将问题逐步扩展到更长的字符串。假设字符串s1和s2的长度分别为m和n，则可以使用一个二维数组dp[m+1][n+1]来存储s1和s2的LCS长度。具体实现如下：

def lcs(s1, s2):
    m = len(s1)
    n = 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])
    return dp[m][n]

在上述代码中，dp[i][j]表示s1[:i]和s2[:j]的LCS长度，如果s1[i-1]等于s2[j-1]，说明s1[i-1]和s2[j-1]都在LCS中，则dp[i][j]等于dp[i-1][j-1]+1；否则，通过比较s1[:i-1]和s2[:j]的LCS长度以及s1[:i]和s2[:j-1]的LCS长度，取其中的最大值作为dp[i][j]的值。

使用字符串“pidancode.com”和“皮蛋编程”作为参数调用上述函数，则可以得到它们的LCS长度为3，对应的LCS为“pda”。