动态规划

from 算法导论（CLRS）

动态规划算法通常用于求解最优值，一般步骤如下：

刻画最优解结构
递归地定义最优解的值
自底向上计算最优解的值
利用计算出的信息构造最优解（构造解本身，可选）

$\text{动态规划与分治方法} \begin{cases} \text{相似：} & \text{组合子问题来求解原问题} \\ \text{不同：} & \text{应用于子问题重叠情况，每个子问题求解一次} \end{cases}$

15.1 钢条切割

给定一段长度为 $n$ 英寸的钢条和一个价格表 $p_i (i = 1, \dots, n)$ 。求切割钢条方案，使销售收益 $r_n$ 最大。

设最优方案为：$n = i_1 + i_2 + \cdots + i_k$，那么最大收益为：

$r_n = p_{i_1} + p_{i_2} + \cdots + p_{i_k}$

一般地，对于 $r_n(n \geq 1)$ ，我们可以用更短的钢条最优切割收益来描述：

$r_n = \max_{1\leq i \leq n}(p_i + r_{n-i})$

这样，为了求解规模为 $n$ 的原问题，我们求解形式完全一样，规模更小的子问题，该问题满足最优子结构性质：

问题的最优解由相关子问题的最优解组合而成，而这些子问题可独立求解。

自顶向下递归实现

采用自顶向下的递归方法实现如下：

def CUT_ROD(p, n):
    if n == 0:
        return 0
    q = 0
    for i in range(n):
        q = max(q, p[i] + CUT_ROD(p, n - i))
    return q

但是显而易见的是，该算法运行效率很差，主要原因在于 CUT_ROD 反复地用相同的参数值对自身进行调用 —— 即它反复求解相同的子问题。其递归调用树如下：

为了具体分析该函数的运行时间，令 $T(n)$ 表示参数值为 $n$ 时的调用次数。该值等于递归调用树中根为 $n$ 的子树中节点总数，那么：

$T(n) = 1 + \sum_{j = 0}^{n-1}{T(j)}$

不难证明：

$T(n) = 2^n$

使用动态规划方法求解最优钢条切割问题

动态规划方法的思想如下：朴素递归算法之所以效率很低，原因在于反复求解相同的子问题。因此，动态规划方法仔细安排求解顺序，对每个子问题只求解一次，并将结果保存起来，如果随后再次需要该子问题的解，只需查找保存的结果，而不必重新计算。因此，动态规划方法是付出额外的内存空间来节省计算时间。

动态规划有两种等价的实现方法：

第一种方法称为带备忘的自顶向下方法。此方法仍按自然的递归形式编写过程，但过程会保存每个子问题的解（通常保存在一个数组或散列表中）。当需要一个子问题的解时，过程首先检查是否已经保存过此解。

def MEMORIZED_CUT_ROD(p, n):
    r = []
    for i in range(n):
        r.append(-1)
    return MEMORIZED_CUT_ROD_AUX(p, n, r):
    
def MEMORIZED_CUT_ROD_AUX(p, n, r):
    if r[n] >= 0:
        return r[n]
    if n == 0:
        q = 0
    else
    	q = -1
    		for i in range(1, n):
                q = max(q, p[i] + MEMORIZED_CUT_ROD_AUX(p, n-i, r))
    r[n] = q
    return q

第二种方法称为自底向上法。这种方法一般需要恰当定义子问题“规模”的概念，使得任何子问题的求解都只依赖于“更小的”子问题的求解。因此我们可以将子问题按规模排序，按由小到大的顺序进行求解。每个子问题只需求解一次，当我们求解它时，它的所有前提子问题都已求解完成。

def BOTTOM_UP_CUT_ROD(p, n):
    r[0] = 0
    for j in range(1, n):
        q = -1
        for i in range(i, j):
            q = max(q, p[i] + r[j-i])
        r[j] = q
    return r[n]

子问题图

当思考一个动态规划问题时，我们应该弄清楚所涉及的子问题及子问题之间的依赖关系。

问题的子问题图准确地表达了这些信息。它是一个有向图，每个顶点唯一地对应了一个子问题。若子问题 $x$ 的最优解需要直接用到子问题 $y$ 的最优解，那么在子问题图中就会有一条从子问题 $x$ 的顶点到子问题 $y$ 的顶点的有向边。

上述问题在 $n = 4$ 时子问题图为：

那么，自底向上动态规划算法是按“逆拓扑排序”来处理子问题图中的顶点。换句话说，对于任何子问题，直到它依赖的所有子问题均已求解完成，才会求解它。

而（带备忘机制的）自顶向下动态规划算法是按照”深度优先搜索“的顺序进行。

子问题图 $G = (V, E)$ 的规模可以帮助我们确定动态规划算法的运行时间。由于每个子问题只求解一次，因此算法运行时间等于每个子问题求解时间之和。通常一个子问题的求解时间与子问题图中对应顶点的度成正比，而子问题的数目等于子问题图的顶点数。因此，通常情况下，动态规划算法的运行时间与顶点和边的数量呈线性关系。

重构解

前文给出的钢条切割问题的动态规划算法返回最优解的收益值，但并未返回解本身。我们可以拓展动态规划算法，使之对每个子问题不仅保存最优收益值，还保存对应的切割方案。利用这些信息，我们就能输出最优解。

def EXTENDED_BOTTOM_UP_CUT_ROD(p, n):
    # let r[0 .. n] and s[0 .. n] be new arrays
    r[0] = 0
    for j in range(1, n):
        q = -1
        for i in range(1, j):
            if q < p[i] + r[j-i]:
                q = p[i] + r[j-i]
                s[j] = i
                r[j] = q
     return (r, s)

数组 $s$ 保存了在求解规模为 $j$ 的子问题中第一段钢条的最优切割长度 $i$。

下面过程将会打印出长度为 $n$ 的钢条切割方案：

def PRINt_ROD_SOLUTION(p, n):
    (r, s) = EXTENDED_BOTTOM_UP_CUT_ROD(p, n)
    while n > 0:
        print(s[n])
        n = n - s[n]

15.2 矩阵链乘法

矩阵链乘法问题可描述为：给定 $n$ 个矩阵的链 $\left\langle A_{1}, A_{2}, \ldots, A_{n}\right\rangle$，矩阵 $A_i$ 的规模为 $p_{i-1} \times p_{i}(1 \leqslant i \leqslant n)$ ，求完全括号化方案，使得计算乘积 $A_1A_2\cdots A_n$ 所需标量乘法次数最少。

注意求解矩阵链乘法问题并不是要真正进行矩阵相乘运算，我们的目标只是确定代价最低的计算顺序，确定最优计算顺序所花费的时间通常要比随后真正进行矩阵相乘所节省的时间要少。

下面用动态规划方法来求解矩阵链的最优括号化方案。

步骤 1：最优括号化方案的结构特征

动态规划方法的第一步是寻找最优子结构，然后利用这种子结构从子问题的最优解构造出原问题的最优解。为方便起见，我们用符号 $A_{i..j}(i \leq j)$ 表示 $A_iA_{i+1}\cdots A_j$ 乘积的结果矩阵。那么，为了对其进行括号化，我们必须在某个 $A_k$ 和 $A_{k+1}$ 之间将矩阵链划分开，也就是对某个整数 $k$ ，我们首先计算矩阵 $A_{i..k}$ 和 $A_{k+1..j}$ ，然后再计算它们的乘积得到最终结果 $A_{i..j}$。

现在我们展示如何利用最优子结构性质从子问题的最优解构造原问题的最优解：为了构造一个矩阵链乘法问题实例的最优解，我们可以将问题划分为两个子问题（$A_iA_{i+1}\cdots A_k$ 和 $A_{k+1}A_{k+2}\cdots A_j$ 的最优括号化问题），求出子问题实例的最优解，然后将子问题的最优解组合起来。我们必须保证在确定分割点时，已经考察了所有可能的划分点，这样就可以保证不会遗漏最优解。

步骤 2：一个递归求解方案

下面用子问题的最优解来递归地定义原问题最优解的代价，我们记 $m[i, j]$ 表示计算矩阵 $A_{i..j}$ 所需标量乘法的最小值，那么：

$m[i, j]=\left\{\begin{array}{ll}{0} & {\text { 如果 } i=j} \\ {\min _{i \leq k<j}\left\{m[i, k]+m[k+1, j]+p_{i-1} p_{k} p_{j}\right\}} & {\text { 如果 } i<j}\end{array}\right.$

$m[i,j]$ 的值给出了子问题最优解的代价，但它并未提供足够的信息来构造最优解。为此我们用 $s[i,j]$ 保存 $A_iA_{i+1}\cdots A_j$ 最优括号化方案的分割点位置 $k$，即使得 $m[i, j]=m[i, k]+m[k+1, j]+p_{i-1} p_{k} p_{j}$ 成立的 $k$ 值。

步骤 3：计算最优代价

现在，我们很容易地基于上述递归公式写出递归算法，但是我们会发现该递归算法是指数时间的，并不比检查所有括号化方案的暴力搜索方法更好。

注意到，我们需要求解的不同子问题的数目是相对较少的：每对满足 $1 \leq i \leq j \leq n$ 的 $i$ 和 $j$ 对应一个唯一的子问题，共有 $\left( \begin{array}{l}{n} \ {2}\end{array}\right)+n=\Theta\left(n^{2}\right)$ 个。递归算法会在递归调用树的不同分支中多次遇到同一个子问题。这种子问题重叠的性质是应用动态规划的另一个标识。

我们将采用自底向上表格法代替递归算法来计算最优代价。

为了实现自底向上方法，我们必须确定计算 $m[i, j]$ 需要访问哪些其他表项。不难发现，算法应该按长度递增的顺序求解矩阵链括号化问题，并按对应的顺序填写表 $m$。对矩阵链 $A_iA_{i+1}\cdots A_j$ 最优括号化的子问题，我们认为其规模为 $j-i+1$。

MATRIX-CHAIN-ORDER(p):
	n = p.length - 1
	let m[1..n, 1..n] and s[1..n-1, 2..n] be new tables
	for i = 1 to n:
		m[i,i] = 0
	for l = 2 to n: 		// l is the chain length
    	for i = 1 to n-l+1:
    		j = i+l-1
    		m[i,j] = inf
    		for k = i to j-1:
    			q = m[i,k] + m[k+1, j] + p[i-1]p[k]p[j]
    			if q < m[i,j]:
    				m[i,j] = q
    				s[i,j] = k
    return m and s

当 $n = 6$ 和矩阵规模如下表时：

$m$ 表和 $s$ 表为：

$\begin{aligned} m[2,5]&=\min {\left\{\begin{array}{l}{m[2,2]+m[3,5]+p_{1} p_{2} p_{5}=0+2500+35 \cdot 15 \cdot 20=13000} \\ {m[2,3]+m[4,5]+p_{1} p_{3} p_{5}=2625+1000+35 \cdot 5 \cdot 20=7125} \\ {m[2,4]+m[5,5]+p_{1} p_{4} p_{5}=4375+0+35 \cdot 10 \cdot 20=11375}\end{array}\right.} \\ &= 7125 \end{aligned}$

步骤 4：构造最优解

虽然上述函数求出了矩阵链乘所需的最少标量乘法运算次数，但它并未直接指出如何进行这种最优代价的矩阵链乘计算。表 $s[1..n-1, 2..n]$ 的每个表项 $s[i,j]$ 记录了一个 $k$ 值，指出 $A_iA_{i+1}\cdots A_j$ 的最优括号化方案的分割点应该在 $A_k$ 和 $A_{k+1}$ 之间。因此我们可以用递归的方式输出最优括号化方案：

PRINT-OPTIMAL-PARENS(s,i,j):
	if i == j:
		print("A" + i)
	else:
		print("(")
		PRINT-OPTIMAL-PARENS(s,i,s[i, j])
		PRINT-OPTIMAL-PARENS(s,s[i, j] + 1,j)
		print(")")

15.3 动态规划原理

本节我们将关注适合使用动态规划方法求解的最优化问题应该具备的两个要素：

最优子结构
子问题重叠

最优子结构

如果一个问题的最优解包含其子问题的最优解，我们就称此问题具有最优子结构性质。使用动态规划方法时，我们用子问题的最优解来构造原问题的最优解因此我们必须小心确保考察了最优解中用到的所有子问题。

原问题的最优解中涉及多少个子问题
在确定最优解使用哪些子问题时，我们需要考察多少种选择

我们可以利用子问题的总数和每个子问题需要考察多少种选择这两个因素的乘积来粗略分析动态规划算法的运行时间。矩阵链乘法问题共有 $\Theta(n^2)$ 个子问题，每个子问题最多需要考察 $n-1$ 中选择，因此运行时间为 $O(n^3)$。

在第 16 章中，我们将介绍贪心算法，它与动态规划算法有很多相似之处，特别是能够应用贪心算法的问题也必须具有最优子结构性质。贪心算法和动态规划算法最大的不同在于它并不是首先寻找子问题的最优解，而是首先做出一次“贪心”选择——在当时（局部）来看是最优的选择，然后求解选出的子问题。

我们在使用动态规划时要小心，特别注意问题是否具有最优子结构性质。最重要的一点是考虑子问题是否无关：同一个原问题的一个子问题的解不影响另一个子问题的解。

重叠子问题

当递归算法会反复地求解相同的子问题，而不是一直生成新的子问题时，我们称最优化问题具有重叠子问题性质。动态规划算法通常利用重叠子问题性质：对每个子问题求解一次，将解存入一个表中，当再次需要这个子问题时直接查表，每次查表的代价为常量时间。

我们考察矩阵链乘法问题，在用递归法求解时，部分递归调用树如下图所示：

不难看出有许多子问题被重复计算了多次。

将此自顶向下的递归算法（无备忘）与自底向上的动态规划算法相比，由于后者利用了重叠子问题性质，要高效的多。

如我们在 15.1 节钢条切割问题中所见，我们可以保持自顶向下策略，同时达到与自底向上动态规划方法相似的效率。思路就是对自然但低效的递归算法加入备忘机制。与自底向上方法一样，我峨嵋你维护一个表记录子问题的解，但仍爆出递归算法的控制流程。下面给出带备忘版本的 RECURSIVE-MATRIX-CHAIN 版本：

MEMORIZED-MATRIX-CHAIN(p):
	n = p.length - 1
	let m[1..n, 1..n] be a new table
	for i = 1 to n:
		for j = 1 to n:
			m[i,j] = inf
	return LOOKUP-CHAIN(m, p, 1, n)
	
LOOKUP-CHAIN(m, p, i, j):
	if m[i,j] < inf:
		return m[i,j]
	if i == j:
		m[i, j] = 0
	else:
		for k = i to j-1:
			q = LOOKUP-CHAIN(m, p, i, k) + 
				LOOKUP-CHAIN(m, p, k+1, j) + p[i-1]p[k]p[j]
			if q < m[i,j]:
				m[i, j] = q
	return m[i,j]

15.4 最长公共子序列

给定一个序列 $X=\left\langle x_{1}, x_{2}, \ldots, x_{m}\right\rangle$，另一个序列 $Z=\left\langle z_{1}, z_{2}, \ldots, z_{k}\right\rangle$ 满足如下条件时称为 $X$ 的子序列：存在一个严格递增的 $X$ 下标序列 $\left\langle\dot{i}_{1}, i_{2}, \cdots, i_{k}\right\rangle$，对所有 $j = 1, 2, \dots, k$，满足 $x_{i_j} = z_j$。

最长公共子序列问题（LCS）：给定两个序列 $X=\left\langle x_{1}, x_{2}, \ldots, x_{m}\right\rangle$ 和 $Y=\left\langle y_{1}, y_{2}, \ldots, y_{n}\right\rangle$，求 $X$ 和 $Y$ 的最长公共子序列。

步骤 1：刻画最长公共子序列的特征

记 $X=\left\langle x_{1}, x_{2}, \ldots, x_{m}\right\rangle$ 的第 $i$ 前缀为 $X_i=\left\langle x_{1}, x_{2}, \ldots, x_{i}\right\rangle$，那么：

定理 15.1 （LCS 的最优子结构） 令 $X=\left\langle x_{1}, x_{2}, \ldots, x_{m}\right\rangle$ 和 $Y=\left\langle y_{1}, y_{2}, \ldots, y_{n}\right\rangle$ 为两个序列，$Z=\left\langle z_{1}, z_{2}, \ldots, x_{k}\right\rangle$ 为 $X$ 和 $Y$ 的任意 LCS

如果 $x_m = y_n$，则 $z_{k}=x_{m}=y_{n}$ 且 $Z_{k-1}$ 是 $X_{m-1}$ 和 $Y_{n-1}$ 的一个 LCS
如果 $x_m \not = y_n$，则 $z_{k} \not =x_{m}$ 意味着 $Z $ 是 $X_{m-1}$ 和 $Y$ 的一个 LCS
如果 $x_m \not = y_n$，则 $z_{k} \not =y_{n}$ 意味着 $Z $ 是 $X$ 和 $Y_{n-1}$ 的一个 LCS

上述定理告诉我们，两个序列的 LCS 包含两个序列的前缀的 LCS。因此，LCS 问题具有最优子结构性质，我们马上还会看到，其递归算法也具有重叠子问题性质。

步骤 2：一个递归解

根据 LCS 问题的最优子结构性质：

$c[i, j]=\left\{\begin{array}{ll}{0} & {\text { if } i=0 \text { or } j=0} \\ {c[i-1, j-1]+1} & {\text { if } i, j>0 \text { and } x_{i}=y_{j}} \\ {\max (c[i, j-1], c[i-1, j])} & {\text { if } i, j>0 \text { and } x_{i} \neq y_{j}}\end{array}\right.$

在之前讨论过的问题中，根据问题的条件，我们没有排除任何子问题，但是在该问题（以及其他类似问题，如编辑距离）中，我们将会根据条件排除子问题。

步骤 3：计算 LCS 的长度

LCS-LENGTH(X,Y):
	m = X.length
	n = Y.length
	let b[1..m, 1..n] and c[0..m, 0..n] be new tables
	for i = 1 to m:
		c[i,0] = 0
	for j = 0 to n:
		c[0,j] = 0
	for i = 1 to m:
	 	for j = 1 to n:
	  		if x[i] == y[j]:
	  			c[i,j] = c[i-1,j-1] + 1
	  			b[i,j] = '↖'
	  		elif c[i-1,j] >= c[i, j-1]:
	  			c[i,j] = c[i-1, j]
	  			b[i,j] = '↑'
	  		else:
	  			c[i,j] = c[i, j-1]
	  			b[i,j] = '←'
	  return c and b

当 $X = ABCBDAB$ 及 $Y = BDCABA$ 时的结果如下图：

过程的运行时间为 $\Theta(mn)$。

步骤 4：构造 LCS

PRINT-LCS(b, X, i, j):
	if i == 0 or j == 0:
		return
	if b[i,j] == "↖":
		PRINT-LCS(b, X, i-1, j-1)
		print x[i]
	elif b[1,j] == "↑":
		PRINT-LCS(b, X, i-1, j)
	else:
		PRINT-LCS(b, X, i, j-1)