第五章动态规划

动态规划算法与分治法类似，其基本思想也是将求解问题分解为若干个子问题。与分治法不同的是，动态规划问题中子问题不是独立的，可能重复计算，所以动态规划旨在优化问题减少重复子问题的计算。
简言之，动态规划的实质是分治和消除冗余。

矩阵链相乘

假设我们要计算三个矩阵的乘积即 $M_1M_2M_3$ ，这 $3$ 个矩阵的维数分别为 $2\times 10,10\times 2,2\times 10$ ，我们可以有 $((M_1M2)M_3),(M_1(M_2M_3))$ 两种方式。前者需要 $2\times 2\times 10=80$ 次乘法，后者需要 $10\times 2\times 10+2\times 10\times 10=400$ 次乘法。可见对于 $n$ 个矩阵 $M_1,M_2...M_n$ 链乘的耗费，取决于 $n-1$ 个乘法的执行顺序。下面我们讨论找出 $n$ 个矩阵链相乘的最小数乘次数。

Catalan数

设 $f(n)$ 是求 $n$ 个矩阵相乘的所有放置括弧的方法数。对于 $(M_1M_2···M_k)\times (M_{k+1}M_{k+2}···M_{n})$ ，对于前 $k$ 个矩阵有 $f(k)$ 种放置方法，对于余下的有 $f(n-k)$ 种放置方法，总共有 $f(k)f(n-k)$ 种放置方法，则对于 $n$ 个矩阵的所有放置方法数：

$f(n)=\sum_{k=1}^{n-1}f(k)f(n-k)$ ，显然 $f(2)=1,f(3)=2$ （两个矩阵只有一种乘法，三个矩阵有两种乘法），我们假定 $f(1)=1$ ，可以证明： $f(n)={1\over n}{\binom{2n-2}{n-1}}$ 。
上述递推式产生了Catalan数，定义 $C_n=f(n+1)$ ，它的前 $11$ 项为： $1,1,2,5,14,42,132,429,1430,4862,16~796$ 。因此矩阵个数 $n$ 逐渐变大时，采用简单的暴力算法是十分低效的。

最小矩阵链乘数MATCHCHAIN

对于每个 $i,1\leq i<n$ ，矩阵 $M_i$ 的列数一定等于矩阵 $M_{i+1}$ 的行数。因此我们指定 $n+1$ 维数 $r_1,r_2,···,r_n,r_{n+1}$ ，其中 $r_i,r_i+1$ 分别表示矩阵 $M_i$ 的行数和列数（最右边的矩阵的列数与前面无关，所以会有 $r_{n+1}$ ）。并且，我们用 $M_{i,j}$ 表示 $M_iM_{i+1}···M_j$ 的乘积， $M_{i,j}$ 的数量乘法耗费记为 $C[i,j]$ 。
设 $k\in (i,j)$ ，那么有 $M_{i,j}=M_{i,k-1}M_{k,j}$ 。显然这样按 $k$ 划分后， $C[i,j]=C[i,k-1]+C[k,j]+M_{i,k-1}M_{k,j}$ （ $M_{i,k-1}M_{k,j}$ 实际上也是两个维数分别为 $r_i\times {r_k}、r_k\times r_{j+1}$ 的新矩阵相乘）。
于是我们得到 $C[i,j]=min\{C[i,k-1]+C[k,j]+r_ir_kr_{j+1}\}$ ，对于求 $M_1M_2···M_n$ ，则我们需要解决递推式 $C[1,n]=min\{C[1,k-1]+C[k,n]+r_1r_kr_{n+1}\}$ 。
为避免重复计算，考虑到 $C[i,j]=C[j,i]$ ，我们将计算二维数组 $C$ 的右上半部分（对角线向上计算），最终 $C[1,n]$ 下图中的 $C[1,6]$ 即为所求。

zeO8P0.png
- 例：给出 $5$ 个矩阵如下：（ $d_0$ 表示第一条对角线）
  
  $M_1:5\times10,M_2:10\times4,M_3:4\times6,M_4:6\times10,M_5:10\times2$
  
  易知， $d_0$ 上的元素均为 $0$ ；
  
  $C[1,2]$
  - $k=2,C[1,2]=0+0+5*10*4=200$
  $C[2,3]$
  - $k=3,C[2,3]=0+0+10*4*6=240$
  ······
  
  $C[1,3]$
  - $k=2,C[1,3]=200+240+5*10*6=740$
  - $k=3,C[1,3]=200+0+5*4*6=320$
  - $C[1,3]=min\{740,320\}=320$
  ······依次计算 $d_1、d_2、···、d_{n-1}$ 得到如下表格：
  
  0 1 2 3 4
  
  C[1,1]=0 C[1,2]=200 C[1,3]=320 C[1,4]=620 C[1,5]=348
  
  C[2,2]=0 C[2,3]=240 C[2,4]=640 C[2,5]=248
  
  C[3,3]=0 C[3,4]=240 C[3,5]=168
  
  C[4,4]=0 C[4,5]=120
  
  C[5,5]=0

0	1	2	3	4
C[1,1]=0	C[1,2]=200	C[1,3]=320	C[1,4]=620	C[1,5]=348
	C[2,2]=0	C[2,3]=240	C[2,4]=640	C[2,5]=248
		C[3,3]=0	C[3,4]=240	C[3,5]=168
			C[4,4]=0	C[4,5]=120
				C[5,5]=0

MATCHCHAIN

输入：n个矩阵的链的维数对应于正整数数组r[1···n+1]。

输出：n个矩阵相乘的数量乘法最小次数。

for i <- 1 to n
    C[i,i] <- 0 #对角线0的元素填充0
end for
for d <- 1 to n-1 #遍历n条对角线
    for i <- 1 to n-d #遍历第d条对角线的所有元素
        j <- i+d
        C[i,j] <- infty
        for k <- i+1 to j #尝试所有可能的k值求min
            C[i,j] <- min{C[i,j], C[i,k-1]+C[k,j]+r[i]r[k]r[j+1]}
        end for
    end for
end for
return C[1,n]

观察MATCHCHAIN算法易知，三层 $for$ 循环嵌套，时间复杂度为 $\Theta(n^3)$ ，算法的空间复杂度取决于所需要的 $r$ 数组，即 $\Theta(n^2)$ 。

0/1背包问题

背包问题的定义如下：设 $U=\{ u_1,u_2,···,u_n\}$ 是 $n$ 项物品的集合，现要将他们放入一个容量为 $C$ 的背包中，对于第 $i$ 个物品， $s_i,v_i$ 分别表示其体积和价值。

数学化描述：给出有 $n$ 项元素的集合 $U$ ，找出一个子集合 $S\subseteq U$ ，使得 $\sum_{u_i\in S}v_i$ 在约束条件 $\sum_{u_i\in S}s_i \leq C$ 下最大。
之所以被称为0/1背包问题，是因为对于集合 $U$ 的每个物品，要么被选中，要么不被选中。
为了装满背包我们给出以下递推式，设 $V[i,j]$ 表示从前 $i$ 项中取出物品放入体积为 $j$ 的背包的最大价值（ $V~means~Value$ ）。显然， $V[0,j]=0$ 因为对于所有体积为 $j$ 的背包，从 $0$ 个物品中取得的最大价值为 $0$ ； $V[i,0]=0$ 因为对于体积为 $0$ 的背包，前 $i$ 项物品无法放入该背包。

$V[i,j]= \begin{cases}0,~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~i=0~or~j=0\\ V[i-1,j],~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~j<s_i\\ max\{V[i-1,j],V[i-1,j-s_i]+v_i\},~~~~~~~~i>0~and~j\geq s_i \end{cases}$
- $V[i-1,j]$ ：当 $j<s_i$ 时，不能再容纳更多的物品，所以 $V[i,j]$ 就为 $i-1$ 的价值；
- $V[i-1,j-s_i]+v_i$ ：当 $j\geq s_i$ 时，可以容纳第 $i$ 个物品，但 $j$ 要腾出 $s_i$ 的体积去容纳第 $i$ 个物品。
例：有容量为 $10$ 的背包，要装入 $5$ 种体积为 $2，3，4，4，6$ 的物品，它们的价值分别是 $4，5，4，7，5$ ，即物品 $a\{3,5\},b\{2,4\},c\{4,4\},d\{4,7\},e\{6,5\}$ 。

znQoPs.png
- 对于 $i=0~orj=0$ 的行和列全部填 $0$ ；
- $i=1$ ，放入 $a$ 物品，由于 $s_a=3$ ，所以从 $j\geq3$ 开始考虑，填入其价值 $v_a=5$ ；
- $i=2$ ，放入 $b$ 物品，由于 $s_b=2$ ，所以从 $j\geq2$ 开始考虑， $j=2$ 得到更新 $V[2-1,2-2]+v_2=4$ ； $j\geq5$ ，均可得到更新 $V[2-1,j-2]+v_2=5+4=9$ ；
- $i=3$ ，放入 $c$ 物品，从 $j\geq4$ 开始考虑，显然把 $ab$ （5）取出放入 $c$ （4）的价值是缩小的······；直到 $j\geq9$ ， $a,b,c$ 可以同时放入价值最大为 $13$ ；
- $i=4$ ，放入 $d$ 物品，从 $j\geq4$ 开始考虑， $ab(5)<d(7)$ 所以更新 $V[4,4]$ ；对于 $V[4,6](a,b)$ ，取出 $a$ 放入 $d$ 的价值更大， $V[4,6]=4+7=11>9$ ······
  
  ······
- 最终依据表格，选择 $a,b,d$ 价值最大为 $16$ ；

背包KNAPSACK算法

KNAPSACK

输入：物品集合U={u1, u2,..., un}，体积分别为s1, s2,..., sn，价值分别为v1, v2,..., vn，容量为C的背包。

输出： $\sum_{u_i\in S}v_i$ 在约束条件 $\sum_{u_i\in S}s_i \leq C$ 下最大， $S\subseteq U$ 。

for i <- 0 to n
    V[i,0] <- 0 
end for
for j <- 0 to C
    V[0,j] <- 0
end for
for i <- 1 to n
    for j <- 1 to C
        V[i,j] <- V[i-1,j]
        if si <= j then V[i,j] <- max{V[i,j], V[i-1,j-si]+vi}
    end for
end for
return V[n,C]

由于计算表格中的每一项需要 $\Theta(1)$ 的时间，所以KNAPSACK算法的时间复杂度为 $\Theta(nC)$ ，空间复杂度为 $\Theta(C)$ 。

所有点对的最短路径问题

设 $G=(V,E)$ 是一个有向图，问题描述为：找出每个顶点到其他所有顶点的距离，这里 $x$ 到 $y$ 的距离是指从 $x$ 到 $y$ 的最短路径长度。
为方便研究，设 $n$ 个顶点在集合 $V=\{1,~2,~...,~n\}$ 中，顶点 $i,j$ 的距离为 $D[i,j]$ 。初始时， $D[i,j]$ 就是有向图的边长 $l[i,j]$ ，若 $i,j$ 不直接连通则 $D[i,j]=\infty$ 。

Floyd算法

对于任意两个顶点 $i,j$ ，它们可以通过其他顶点间接连通，所以我们可以通过比较 $i,j$ 直接连通的长度与 $i,j$ 通过顶点 $k$ 间接连通的长度，选取较小值。当然，顶点 $i,j$ 间接连通不一定只经过一个顶点 $k$ ，这是一个递归过程。
开始时，如果 $i\neq j$ 并且 $(i,j)$ 是 $G$ 中的边，则置 $D_0[i,i]=0,D_0[i,j]=l[i,j]$ ，否则置 $D_0[i,j]=\infty$ 。然后顺序迭代 $n$ 次， $D_k[i,j]$ 表示从顶点 $i$ 到 $j$ 的距离，且经过的中间顶点编号不大于 $k$ ，则：

$D_k[i,j]=min\{ D_{k-1}[i,j], D_{k-1}[i,k]+D_{k-1}[k,j] \}$

FLOYD

输入：以矩阵 $l$ 表示的有向图G。

输出：矩阵D，使得D[i,j]表示顶点i到顶点j的距离。

D <- l #将l复制到矩阵D
for k <-  1 to n
    for i <- 1 to n
        for j <- 1 to n
            D[i,j]=min{D[i,j], D[i,k]+D[k,j]} #看是原距离更小，还是加入顶点k后更小
        end for
    end for
end for
return D

例如，考虑如下有向图，求矩阵 $D$ 。

zn8nJJ.png
- $D_0$ 即为有向图 $G$ （ $D_0$ 中的 $D[3,3]=0$ ，图片错误）；
- $k=1$ ，以 $1$ 为媒介重新计算距离，对于 $D[2,3]$ ，若借助顶点 $1$ 距离为 $8+9=17>6$ 所以不变；对于 $D[3,2]$ ，借助顶点 $1$ 距离为 $1+2=3< \infty$ 得到更新；
  
  ······