动态规划

gaunthan Posted on Aug 7 2016

? Algorithm Design Techniques ?

##  概述
**动态规划**（dynamic programming）与**[分治法](http://leanote.com/blog/post/58a7b354ab6441489f003b6f)**(divide and conquer)相似，都是通过组合子问题的解来求解原问题。分治法将问题划分为互不相交的子问题，递归地求解子问题，再将它们的解组合起来，求出原问题的解。与此相反，动态规划应用于子问题重叠的情况，即不同的子问题具有公共的子子问题（子问题的求解是递归进行的，将其划分为更小的子子问题）。在这种情况下，分治算法会做许多不必要的工作，它会反复地求解那些公共子子问题。而动态规划算法对每个子子问题只求解一次，将其解保存在一个表格中，从而无需每次求解一个子子问题时都要重新计算，避免了这种不必要的计算工作。

动态规划方法通常用来求解**最优化问题**（optimization problem）。这类问题可以有很多可行解，每个解都有一个值，我们希望寻找具有最优值（最小值或最大值）的解。我们称这样的解为问题的**一个最优解**（an optimal solution），而不是**最优解**（the optimal solution），因为可能有多个解都达到最优值。

通常按如下4个步骤来设计一个动态规划算法：

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

步骤1~3是动态规划算法求解问题的基础。如果我们仅仅需要一个最优解的值，而非解本身，可以忽略步骤4。如果确实要做步骤4，有时就需要在执行步骤3的过程中维护一些额外信息，以便用来构建一个最优解。

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

* 带备忘的自顶向下法
* 自底向上法

两种方法得到的算法具有相同的渐进运行时间，仅有的差异是在某些特殊情况下，自顶向下方法并未真正递归地考察所有可能的子问题。由于没有频繁的递归函数调用的开销，自底向上方法的时间复杂性函数通常具有更小的系数。

## 带备忘的自顶向下法
**带备忘的自顶向下法**（top-down with memoization）按自然的递归形式编写过程，但过程会保存每个子问题的解（通常保存在一个数组或散列表中）。当需要一个子问题的解时，过程首先检查是否已经保存过此解。如果是，则直接返回保存的值，从而节省了计算时间；否则，按通常方式计算这个子问题，然后保存该子问题的解。

## 自底向上法
**自底向上法**（bottom-up method）一般需要恰当定义子问题的“规模”的概念，使得任何子问题的求解都只依赖于“更小的”子问题的求解。因而我们可以将子问题按规模排序，按由小至大的顺序进行求解。当求解某个子问题时，它所依赖的那些更小的子问题都已求解完毕，结果已经保存。每个子问题只需求解一次，当我们求解它（也是第一次遇到它）时，它的所有前提子问题都已求解完成。

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

问题的**子问题图**准确地表达了这些信息。子问题图是一个有向图，每个顶点唯一地对应一个子问题。若求子问题x的最优解时需要直接用到子问题y的最优解，那么在子问题图中就会有一条从子问题x的顶点到子问题y的顶点的有向边。我们可以将子问题图看作自顶向下递归调用树的“简化版”或收缩版，因为树中所有对应相同子问题的结点合并为图中单一顶点，相关的所有边都从父结点指向子结点。

子问题图的一个示意如下：
![](https://leanote.com/api/file/getImage?fileId=587cdf57ab6441777100023c)

自底向上的动态规划方法处理子问题图中顶点的顺序为：对于一个给定的子问题x，在求解它之前求解邻接至它的子问题y。自底向上动态规划算法是按**逆拓扑序**（reverse topological sort）或**反序的拓扑序**（topological sort of the transpose）来处理子问题图中的顶点。换句话说，对于任何子问题，直至它依赖的所有子问题均已求解完成，才会求解它。类似地，我们可以用**深度优先搜索**（depth-first search）来描述（带备忘机制的）自顶向下动态规划算法处理子问题的顺序。

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

## 钢条切割问题
### 描述
给定一段长度为n英寸的钢条和一个价格表$p_i(i = 1, 2, ···, n)$，求切割钢条方案，使得销售收益$r_n$最大。注意，如果长度为n英寸的钢条的价格$p_n$足够大，最优解可能就是完全不需要切割。

### 分析
长度为n英寸的钢条共有$2^{n-1}$种不同的切割方案，因为在距离钢条左端$i(i = 1, 2, ···, n-1)$英寸处，总是可以选择切割或不切割。如果用普通的加法符号表示切割方案，那么如果一个最优解将钢条切割为k段（$1 \le k \ge n$），则最优解切割方案为

$$n = i_1 + i_2 + ··· + i_k $$

将钢条切割为长度分别为$i_1，i_2，···，i_k$的小段，得到最大收益

$$r_n = p_{i_1} + p_{i_2} + ··· + p_{i_k}$$

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

$$r_n = max(p_n，r_1 + r_{n-1}，r_2 + r_{n-2}，···，r_{n-1} + r_1) $$

第一个参数$p_n$对应不切割，直接出售长度为n英寸的钢条的方案。其他n-1个参数对应另外n-1种方案：对每个$i(i = 1, 2, ···, n-1)$，首先将钢条切割为长度为$i$和$n-i$的两段，接着求解这两段的最优切割收益$r_i$和$r_{n-i}$（每种方案的最优收益为两段的最优收益之和）。由于无法预知哪种方案会获得最优收益，我们必须考察所有可能的$i$，选取其中收益最大者。如果直接出售原钢条会获得最大收益，我们当然可以选择不做任何切割。

注意到，为了求解规模为n的原问题，我们先求解形式完全一样，但规模更小的子问题。即当完成首次切割后，我们将两段钢条看成两个独立的钢条切割问题实例。通过组合两个相关子问题的最优解，并在所有可能的两段切割方案中选取组合收益最大者，构成原问题的最优解。

钢条切割问题满足**最优子结构**（optimal substructure）性质：问题的最优解由相关子问题的最优解组合而成，而这些子问题可以独立求解。

### 自顶向下递归实现
除了上述求解方法外，钢条切割问题还存在一种相似的但更为简单的递归求解方法：我们将钢条从左边切割下长度为i的一段，只对右边剩下的长度为n-i的一段继续进行切割（递归求解），对左边的一段则不再进行切割。这样，不做任何切割的方案就可以描述为：第一段的长度为n，收益为$p_n$，剩余部分长度为0，对应的收益为$r_0 = 0$。于是可以得到上面公式的简化版本：

$$r_n = max(p_i + r_{n-i})$$

在此公式中，原问题的最优解只包含一个相关子问题的解，而不是两个。伪代码描述见下：

```
CUT-ROD(p, n)
    if n == 0
        return 0
    q = -∞
    
    for i = 1 to n
        q = max(q, p[i] + CUT-ROD(p, n - i))
    return q
```

假设$T(n)$表示第二个参数值为0时CUT-ROD的调用次数，此值等于递归调用树中根为n的子树中的结点总数，注意，此值包含了根结点对应的最初的一次调用。因此$T(0) = 1$，且
$$T(n) = 1 + \sum_{j=0}^{n-1}T(j)$$
容易证明CUT-ROD的运行时间效率$T(n)\in2^n$。

### 使用动态规划方法
可以看到，朴素递归算法效率很低，因为它反复求解相同的子问题。因此，动态规划方法仔细安排求解顺序，对每个子问题只求解一次，并将结果保存下来。如果随后再次需要子问题的解，只需查找保存的结果，而不必重新计算。因此，动态规划方法是付出额外的内存空间来节省计算时间，是典型的**时空权衡**（time-memory trade-off）的例子。而时间上的节省可能是非常巨大的：可能将一个指数时间的解转化为一个多项式时间的解。如果子问题的数量是输入规模的多项式函数，而我们可以在多项式时间内求解出每个子问题，那么动态规划方法的总运行时间就是多项式阶的。

#### 加入备忘机制
下面给出的是自顶向下CUT-ROD过程的伪代码，加入了备忘机制：
```cpp
MEMOIZED-CUT-ROD(p, n)
    let r[0..n] be a new array
    for i = 0 to n
        r[i] =  -∞
    return MEMOIZED-CUT-ROD-AUX(p, n, r)
    
MEMOIZED-CUT-ROD-AUX(p, n, r)
    if r[n] >= 0
        return r[n]
    if n == 0
        q = 0
    else
        q = -∞
        for i = 1 to n
            q = max(q, p[i] + MEMOIZED-CUT-ROD-AUX(p, n - i, r))
    r[n] = q
    return q
```

#### 自底向上版本
自底向上版本更为简单：
```
BOTTOM-UP-CUT-ROD(p, n)
    let r[0..n] be a new array
    r[0] = 0
    for j = 1 to n
        q = -∞
        for i = 1 to j
            q = max(q, p[i] + r[j - i])
        r[j] = q
    return r[n]
```
自底向上版本BOTTOM-UP-CUT-ROD采用子问题的自然顺序：若$i<j$，则规模为$i$的子问题比规模为$j$的子问题“更小”。因此，过程依次求解规模为$j = 0, 1, ···, n$的子问题。

自底向上算法和自顶向下算法具有相同的渐进运行时间，都属于$\theta(n^2)$。

### 重构解
前文给出的钢条切割问题的动态规划算法返回最优解的收益值，但并未返回解本身（一个长度列表，给出切割后每段钢条的长度）。我们可以扩展动态规划算法，使之对每个子问题不仅保存最优收益值，还保存对应的切割方案。利用这些信息，就能输出最优解。实际的做法是：
```
EXTENDED-BOTTOM-UP-ROD(p, n)
    let r[0..n] and s[0..n] be new arrays
    r [0] = 0
    for j = 1 to n
        q = -∞
        for i = 1 to j
            if q < p[i] + r[j - i]
                q = p[i] + r[j - i]
                s[j] = i 
        r[j] = q
    return r and s
```

## References

- MarkAllenWeiss, 韦斯. 数据结构与算法分析:C语言描述[M]. 机械工业出版社, 2010.
- ThomasH.Cormen. 算法导论[M]. 机械工业出版社, 2013.
- [【算法】动态规划问题集锦与讲解](https://segmentfault.com/a/1190000004498566).