15. 动态规划

动态规划和分治法相似，都是通过组合子问题的解来求解原问题的解。但不同的是分治法将问题划分为不相交的子问题，递归的求解子问题，再将它们的解组合起来，求出原问题的解。相反，动态规划应用于子问题相互重叠的情况，即不同的子问题具有公共的子子问题。这种情况下，用分治法会反复的求解相同的子问题，造成时间浪费。动态规划对每个子问题只求解一次，并且保存在表格中，从而避免重复计算。

动态规划通常用于求解最优化问题。

我们通常按照如下步骤设计一个动态规划算法：

1. 刻画一个最优解的结构特点
2. 递归的定义最优解的值
3. 计算最优解的值，通常采用自底而上的方法
4. 利用计算出的信息构造一个最优解

如果只需要最优解的值，而非最优解本身，可忽略第四步。如果需要做第四步，往往需要在执行第三步时维护一些额外信息。

钢条切割

钢条切割问题：给定一段长度为n英寸的钢条和一个价格表p_i(i=1,2…n)，求切割方案使得收益r_n最大。

考虑当n=4时，所有的切割方案如下，我们发现当把4英寸的钢条切割为两段2英寸长的钢条时产生的收益最大。

当区分1+3切法和3+1切法时，n英寸的钢条有2^n-1种切割方案。
我们可以手动得到r_i，及对应切割方案：

对于r_n，我们可以用更短的钢条的最优切割收益来描述它：
rn=max(pn,r1+rn−1,r2+rn−2,...,rn−1+r1).$r_n=max(p_n,r_1+r_{n-1},r_2+r_{n-2},...,r_{n-1}+r_1).$

这时我们找到了钢条切割问题的最优子结构。每次切割后我们可以把切开的两段钢条看做独立的钢条切歌问题。一段钢条的最优解为所有切割方案中最大的。
我们可以将r_n的式子简化为：rn=max1≤i≤n(pi+in−i)$r_n=\underset{1\le i\le n}{max}(p_i+i_{n-i})$ .

自顶而下的递归实现

根据上面的式子，我们可以得到下面这种自顶而下的递归实现（p为价格数组）：

这种实现的递归式为：T(n)=1+∑j=0n−1T(j).$T(n)=1+\sum _{j=0}^{n-1}T(j).$
我们可以求得T(n)=2i$T(n)=2^i$，这个时间是非常惊人的，而这么大的原因就是因为包含了非常多的重复计算。下图是递归树，红线圈起来的都是重复计算部分。

使用动态规划方法

• 带备忘的自顶而下法
  与前面的递归方法类似，但是用了一个数组r[1..n]记录最优解，如果发现r[n]已经有记录，则无需重复计算，直接返回该值。
  
• 自底而上法
  自底而上法采用子问题的自然顺序，依次求解规模为j=1,2…,n的子问题。
  

无论是带备忘的自顶而下法还是自底而上法，其中都是用了一个额外数组来存储子问题的最优解，从而避免重复计算子问题的解。动态规划付出额外的内存空间来节省时间，是典型的时空权衡的例子。

子问题图

当思考动态规划问题时，弄清所涉及子问题及子问题之间的依赖关系很关键。
问题的子问题图准确的表达了这些信息：

途中结点表示钢条切割的子问题规模，箭头表示子问题之间的依赖关系。
有了子问题图，我们便可轻易的得知自底而上的顺序应该如何。
而且子问题图G=(V, E)还可以帮助我们确定动态规划算法的运行时间。由于每个子问题只求解一次，因此算法运行时间等于每个子问题求解时间之和。通常，一个子问题的求解时间与子问题图中对应顶点的度（射出边的数目）成正比，而子问题的数目等于子问题图的顶点数。因此，通常情况下，动态规划算法的运行时间与顶点和边数量呈线性关系。

重构解

前面的方法只给出的如何求出最优解的值，但并未返回解本身。
下面是基于自底而上动态规划算法的扩展，其中用数组s[0..n]存储n英寸钢条的最优切割方案，s[i]存储的数字表示，i英寸的钢条切割为s[i]英寸和i-s[i]英寸时最优，其中s[i]英寸部分不再切割，i-s[i]英寸部分的最优解需要递归查看。
所以可以通过PRINT-CUT-ROD-SOLUTION来打印出n英寸钢条的一个最优切割方案。

矩阵链乘法

给定一个n个矩阵的序列（矩阵链）<A1,A2,...,An>$<A_1,A_2,...,A_n>$，我们希望求他们的乘积A1A2...An$A_1{A}_2...A_n$，由矩阵乘法的结合律我们可知给乘积链随意的加上括号不会改变最终的结果，但是不同的括号会影响矩阵链乘法的时间。
以矩阵链<A1,A2,A3>$<A_1,A_2,A_3>$为例，三个矩阵的规模分别是10×100、100×5和5×50。如果按照((A1A2)A3)$((A_1{A}_2)A_3)$的顺序计算，A1A2$A_1{A}_2$（规模10×5）需要做10×100×5=5000次标量乘法，再与A3$A_3$相乘又需要10×5×50=2500次标量乘法，总共需要7500次标量乘法。如果按照(A1(A2A3))$(A_1(A_2{A}_3))$的顺序计算，A2A3$A_2{A}_3$（规模100×50）需要做100×5×50=25000次标量乘法，A₁再与之相乘又需要10×100×50=50000次标量乘法，总共需要75000次标量乘法。因此，按照((A1A2)A3)$((A_1{A}_2)A_3)$的顺序比按照(A1(A2A3))$(A_1(A_2{A}_3))$的顺序快了10倍。
所以引入了矩阵链乘法问题：给定n个矩阵的链<A1,A2,...,An>$<A_1,A_2,...,A_n>$，矩阵i的规模为pi−1×pi$p_{i-1}\times p_i$，求一个完全括号化方案，使得计算乘积A1A2...An$A_1{A}_2...A_n$所需的标量乘法次数最少。

我们可以用下面这个递归式表示矩阵链完全括号化方案的个数，这个递归式的解为Θ(2n)$\mathrm{\Theta }(2^n)$，所以穷举法是不可行的。

动态规划法

1. 刻画一个最优解的结构特点
   用Ai..j$A_{i..j}$表示AiAi+1...Aj$A_i{A}_{i+1}...A_j$。我们可以将Ai..j$A_{i..j}$分解为子问题Ai..k$A_{i..k}$和Ak+1..j$A_{k+\mathrm{1..}j}$，即AiAi+1...Aj−>(AiAi+1...Ak)(Ak+1Ak+2...Aj)$A_i{A}_{i+1}...A_j->(A_i{A}_{i+1}...A_k)(A_{k+1}{A}_{k+2}...A_j)$。然后在对子问题递归求解。
2. 递归的定义最优解的值
   用m[i,j]$m[i,j]$表示Ai..j$A_{i..j}$所需标量乘法次数的最优值。假设Ai..j$A_{i..j}$的最优分割点为k(i<=k<j)$k(i<=k<j)$，那么m[i,j]=m[i,k]+m[k+1,j]+pi−1pkpj$m[i,j]=m[i,k]+m[k+1,j]+p_{i-1}{p}_k{p}_j$，然而这个分割点我们是不知道的，但是肯定在i和j之间，我们只需找到所有可能中的最小值，所以我们有如下递归式：

3. 计算最优解的值，通常采用自底而上的方法
从上面的递归式能推测出自底而上法的顺序，或者使用子问题图辅助。可以从链长为2的子问题开始求解，一直递增到链长为n的子问题，Done。伪代码如下：

使用m[i,j]存储A_i..j的最优解的值，s[i,j]存储A_i..j的最优分割点k。

4. 利用计算出的信息构造一个最优解
利用s数组存储的最优分割点，我们可以递归的构造出一个最优解，伪代码如下：

动态规划原理

虽然已经介绍了两个动态规划问题，但可能还会疑惑到底什么样的问题可以使用动态规划方法解决？
适合用动态规划的最优化问题应该具备两个要素：最优子结构和子问题重叠

最优子结构

动态规划法的第一步便是刻画最优解的结构。如果一个问题的最优解包括子问题的最优解，我们称此问题具有最优子结构性质。
发掘最优子结构性质的过程遵循如下通用模式：
1. 证明问题最优解的第一个组成部分是做出一个选择
2. 对于一个给定问题，假定已经知道哪种选择会得到最优解
3. 给定可获得最优解的选择后，确定这次选择会产生哪些子问题，以及如何最好的刻画子问题空间
4. 利用“剪切-粘贴”技术证明：作为构成原问题最优解的组成部分，每个子问题的解就是它本身的最优解。

利用反证法：假设子问题的解不是其最优解，那么我们可以“剪切”掉这个非最优解，将最优解“粘贴”进去，从而得到一个更优的解，这与最初的解是原问题最优解的前提假设矛盾。

对于不同问题领域，最优子结构的不同体现在：
1. 原问题的最优解涉及多少个子问题（一个问题分解为多少个子问题）
2. 在确定最优解使用那些子问题时，我们需要考虑多少种选择（有多少种分解方式）

重叠子问题

如果递归算法反复求解相同的子问题，我们就称最优化问题具有重叠子问题性质。与之相对的，适合用分治法求解的问题通常在递归的每一步都生成全新的子问题。
动态规划通常这样利用重叠子问题的性质：对每个子问题只求解一次，将解存入一个表中，当再次需要这个子问题时直接查表，查表的代价为常数时间。

最长公共子序列

一个给定序列的子序列是降给定序列中零个或者多个元素去掉后的结果。
给定两个序列X和Y，如果Z既是X的子序列，又是Y的子序列，那么Z为X和Y的公共子序列。
最长公共子序列问题给定两个序列X={x₁, x₂, …, x_m}和Y={y₁, y₂, …, y_n}，求X和Y长度最长的公共子序列。

1. 刻画一个最优解的结构特点
   
2. 递归的定义最优解的值

3. 计算最优解的值，通常采用自底而上的方法

c[i, j] 存储序列X_1->i和Y_1->j最长公共子序列的长度
b[i, j] 存储序列X_1->i和Y_1->j最优解依赖的子问题的方向
4. 利用计算出的信息构造一个最优解

当b[i, j]存储的是“↖”时，表示x_i和y_j相同。
所以从b[m, i]开始，训着箭头方向查找“↖”，便可以找到一个最长公共子序列。
伪代码如下：

涉及算法

点击查看实现
+ 钢条切割
+ 矩阵链乘法
+ 最长公共子序列