Python 中的动态规划（DP）简介

动态规划（DP）是一种解决复杂问题的算法思想，适用于优化问题和决策问题。在DP中，通过将问题分解成子问题并在求解子问题时保存中间结果，可以避免重复计算，并提高效率。在Python中，可以使用字典、列表等数据结构存储中间结果，然后利用它们来计算最终结果。

一个典型的DP问题可以用“最长公共子序列”（Longest Common Subsequence）来说明。题目是这样的：给定两个字符串s1和s2，求它们的最长公共子序列。例如，当s1="pidancode"，s2="皮蛋编程"时，它们的最长公共子序列是"pianco"。

解决这个问题的DP方法可以分为以下几个步骤：

1. 定义状态：定义一个二维数组dp，dp[i][j]表示s1的前i个字符与s2的前j个字符的最长公共子序列的长度。

2. 初始化状态：当任意一个字符串为空时，其最长公共子序列长度为0，因此dp[i][0]和dp[0][j]都应该初始化为0。

3. 状态转移方程：当s1[i]==s2[j]时，dp[i][j] = dp[i-1][j-1] + 1，即最长公共子序列在s1[i]和s2[j]处各增加一个相同字符；否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])，即最长公共子序列在s1[i]和s2[j]处至少有一个字符不包含，因此可以分别考虑s1[i]和s2[j]之前的最长公共子序列，取其中较长的一个即可。

4. 返回结果：dp[-1][-1]即为最长公共子序列的长度。

以下是Python代码实现：

def longest_common_subsequence(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n+1) for i 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[-1][-1]

使用上面的例子进行验证：

s1 = "pidancode"
s2 = "皮蛋编程"
print(longest_common_subsequence(s1, s2))
# output: 6

这里的dp数组为：

     空  皮  蛋  编  程
空   0  0   0   0   0 
p    0  0   0   0   0
i    0  0   0   0   0
d    0  0   0   0   0
a    0  0   0   0   0
n    0  0   0   0   0
c    0  0   0   0   0
o    0  0   0   0   0
d    0  0   0   0   0
e    0  0   0   0   0

其中，dp[1][2]=1，表示s1的前1个字符“p”与s2的前2个字符“皮”之间的最长公共子序列长度为1；dp[2][3]=2，表示s1的前2个字符“pi”与s2的前3个字符“皮蛋”之间的最长公共子序列长度为2；以此类推，最终dp[9][4]=6，即最长公共子序列长度为6。