3.6.3 动态规划
动态规划是分治算法的一个衍生，它将一个问题切分成多个更加简单的子问题，然后按照顺序逐个解决。对于每个子问题，它只求解一次，然后将结果存储起来以供后续使用，这样可以避免重复计算。此外，动态规划在计算当前解时，会结合较小规模的子问题的解，并且不断增加子问题的规模。很多情况下，最终计算出来的解即为全局最优解。
动态规划常用于求解最值优化类问题上。下面通过一个示例来阐释动态规划算法。
科学家经常通过比对DNA序列来确定其相似性。现有这样一个DNA序列——由A、C、T、G所组成。因此，一个DNA序列就可以使用一个字符串进行表示，而DNA序列的相似性就可以转化成计算两个字符串的最小编辑距离。也就是说，给定一个字符串s1和一个目标字符串s2，需要使用最少的编辑操作来将s1转化成s2。支持的编辑操作包括：
例如字符串s1为“GCTAC”，可以通过3次编辑操作来得到目标字符串“CTCA”：
当然，还有其他方式来得到目标字符串，但是最少也需要3次编辑操作。对于初学者来说，计算出需要操作的次数就已经足够了，我们暂时还不需要计算出具体的操作顺序。
动态规划的关键点是存储子问题的结果。在这个例子中，我们可以使用一个二维矩阵mi，来记录s1的前i个字符和s2的前j个字符之间的最小编辑距离。这个矩阵可以初始化为：
在这个矩阵中，行标为i，列标为j。以m0为例，这个元素表示的是s1的前0个字符（也就是空字符串）和s2的前4个字符串（整个字符串“CTCA”）之间的最小编辑距离。可以很容易计算出来，m0的值为4，因为我们需要插入全部s2的4个字符到s1中去。同样的，我们也可以轻易得到m3的值为3，因为从s1的前3个字符来考虑，我们需要删除这所有3个字符来得到s2的前0个字符（即空字符串）。
动态规划的巧妙之处在于如何不断地从规模较小的子问题的解中构建出当前的最优解。让我们先来看看m1，这是表示s1的第一个字符G和s2的第一个字符C之间的编辑距离，现在有3个选择：
我们肯定会选择操作数最小的，所以m1=1。那么怎么推广这个选择策略呢？试考虑图3-2所示的计算过程。
每一次计算mi时都面临3个选择：
现在我们脑海里面就应该有一幅图片，生动地描述了动态规划是如何一步一步地按照既定的顺序从小规模的子问题开始逐渐处理的（即，从第一行到最后一行，每行按照最左到最右的顺序访问，如例3-3所示）。计算过程是按照行标i从1到len(s1)逐渐进行。当矩阵m初始化之后，我们利用嵌套的for循环计算每个子问题的最优解，直到m中的所有值都已经计算完毕。这个过程通常不用递归，而是会将之前计算过的结果存储起来。最终的最优解即为mlen(s1)的值。
图3-2：计算mi
例3-3：使用动态规划计算最小编辑距离（Python）
def minEditDistance(s1, s2):
"""计算将s1转换到s2的最小编辑距离"""
len1 = len(s1)
len2 = len(s2)
创建一个二维结构 满足mi = 0, 0≤i≤len1, 0≤j≤len2
m = [None] * (len1 + 1)
for i in range(len1 + 1):
m[i] = [0] * (len2 + 1)
横向、纵向设置初始化操作次数
for i in range(1, len1 + 1):
m[i][0] = ifor j in range(1, len2 + 1):
m[0][j] = j
计算最优解
for i in range(1, len1 + 1):
for j in range(1, len2 + 1):
cost = 1
if s1[i - 1] == s2[j - 1]: cost = 0
replaceCost = m[i - 1][j - 1] + cost
removeCost = m[i - 1][j] + 1
insertCost = m[i][j - 1] + 1
m[i][j] = min(replaceCost, removeCost, insertCost)return mlen1
表3-5给出了矩阵m的最终值。
表3-5：所有子问题的解
例如m3=1，因为字符串“GCT”和“CT”的最小编辑距离只有1，仅仅需要删掉GCT的第一个字符即可。这段代码仅仅计算了最小编辑距离，如果需要记录操作顺序，那么就需要另外一个矩阵prev来存储。previ记录了在计算mi时所选择的3个操作中的哪一个。要恢复操作，我们可以从mlen(s1)开始，使用previ的值，一步一步地向后追溯，直到m0为止。修改过的代码见例3-4。
例3-4：使用动态规划计算最小编辑距离，并且记录操作顺序
REPLACE = 0
REMOVE = 1
INSERT = 2
def minEditDistance(s1, s2):
"""计算将s1转换到s2的最小编辑距离，并且记录操作顺序 """
len1 = len(s1)
len2 = len(s2)
创建一个二维结构满足mi = 0, 0≤i≤len1, 0≤j≤len2
m = [None] * (len1 + 1)
op = [None] * (len1 + 1)
for i in range(len1 + 1):
m[i] = [0] * (len2 + 1)
op[i] = [-1] * (len2 + 1)
横向、纵向设置初始化代价
for j in range(1, len2 + 1):
m[0][j] = jfor i in range(1, len1 + 1):
m[i][0] = i
计算最优解
for i in range(1, len1 + 1):
for j in range(1, len2 + 1):
cost = 1
if s1[i - 1] == s2[j - 1]: cost = 0
replaceCost = m[i - 1][j - 1] + cost
removeCost = m[i - 1][j] + 1
insertCost = m[i][j - 1] + 1
costs = [replaceCost, removeCost, insertCost]
m[i][j] = min(costs)
op[i][j] = costs.index(m[i][j])ops = []
i = len1
j = len2
while i != 0 or j != 0:
if op[i][j] == REMOVE or j == 0:
ops.append('remove {}-th char {} of {}'.format(i,s1[i-1],s1))
i = i - 1
elif op[i][j] == INSERT or i == 0:
ops.append('insert {}-th char {} of {}'.format(j,s2[j-1],s2))
j = j - 1
else:
if m[i - 1][j - 1] < m[i][j]:
fmt='replace {}-th char of {} ({}) with {}'
ops.append(fmt.format(s1, i, s1[i - 1], s2[j - 1]))
i, j = i - 1, j - 1return mlen1, ops
