动态规划 Dynamic Programming

算法导论笔记

programming 指的是一种表格法，并非编写计算机程序

动态规划与分治方法相似，都是通过组合子问题的解来求解原问题。但是分治法将问题划分为互不相交的子问题。而动态规划是应用与子问题重叠的情况，即不同的子问题有着公共的子子问题（子问题的求解是递归进行的，将其划分为更小的子子问题）。

动态规划通常用于求解最优化问题，这类问题通常可以有很多可行解，每个解都有一个值，我们希望寻找具有最优值的解。我们将这样的解称之为问题的一个最优解，而不是最优解，因为最优解不唯一。

动态规划设计步骤

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

钢条切割

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

分析问题：长度为n的钢条共有$2^{n-1}$种不同的切割方案（如果没有切割顺序则包含重复方案）（在每个节点我们总是可以选择切割或者不切割）

我们可以用更短的钢条的最优切割收益来描述它：

第一种方案表示不切割，其余方案表示：对每个$i=1,2,..,n-1$，首先将钢条切割为长度为$i$和$n-i$的两段，接着求$r_i$和$r_{n-i}$.因为无法预知哪种方案会获得最优收益，我们必须考虑所有可能的$i$，选取其中收益最大者。

可以看到，为了求解规模为n的原问题，我们先求解形式完全一样，但规模更小的子问题。即当完成首次切割后，我们将两段钢条看做两个独立的钢条切割问题。我们通过组合两个相关子问题的最优解，并在所有可能的两端钢条切割方案选取收益最大者，构成原问题的最优解。这里我们称钢条切割问题满足最优子结构（optimal substructure）：问题的最优解由相关的子问题的最优解组合而成，而这些子问题可以独立求解。

除了上面的方法，钢条切割还有一个更为简单的递归方法：我们先将钢条从左边切割下长度为$i$的一段，只对优鞭剩下的长度为$n-i$的一段继续进行切割（递归求解）

自顶向下递归实现：

xxxxxxxxxx
# p:价格数组
# n：钢条长度
CUT-ROD(p,n)
    if n == 0
        return 0
    else
        q = -Inf
        for i = 1 to n
            q = max(q, p[i]+CUT-ROD(p,n-i))
        return q 

不难证明CUT-ROD的运行时间是n的指数函数，存在重复计算子问题。

动态规划

可知，朴素递归算法之所以效率低下，是因为反复求解相同的子问题。而动态规划方法是付出额外的内存空间来节省时间，是典型的时空权衡（time-memory trade-off）的例子。在这个问题上，动态规划的方法可以将指数时间的解转化为一个多项式时间的解。如果子问题的数量是输入规模的多项式函数，而我们可以在多项式时间内求解出每个子问题，那么总运行时间就是多项式的。

1. 带备忘的自顶向下法（top-down with memoization）(备忘的意思，源自memo)

   在递归的方法下，保存每个子问题的求解，这样不用反复求解子问题。

   xxxxxxxxxx
   MEMOIZED-CUT_ROD(p,n)
       r = array[0..n]
       for i = 0 to n
           r[i] = -inf
       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
           return 0
       else
           q = -inf
           for i = 1 to n
               q = max(q, p[i]+MEMOIZED-CUT-ROD-AUX(p,n-i,r))
           r[n] = q
           return q
   

2. 自底向下法（bottom-up method）

   xxxxxxxxxx
   BOTTOM-UP-CUT-ROD(p,n)
       r = array[0..n]
       for i = 0 to n
           r[i] = 0
           for j = 0 to i
               r[i] = max(r[i], p[j] + r[i-j])
       return r[n]
   

重构解

前面虽然计算出了最佳的收益，但是还没有给出切割方案

以自底向下法为例(新增s数组保存第一段的切割长度)：

xxxxxxxxxx
BOTTOM-UP-CUT-ROD(p,n)
    r = array[0..n]
    s = array[0..n]
    for i = 0 to n
        r[i] = 0
        for j = 0 to i
            if p[j] + r[i-j] > r[i]:
                r[i] = p[j] + r[i-j]
                s[i] = j
    return r and s
​
PRINT-CUT-ROD(p,n)
    r, s = BOTTOM-UP-CUT-ROD(p,n)
    while n > 0
        print(s[n-1])
        n = n - s[n-1]  

矩阵链乘法

问题：给定n个矩阵的链$<A_1,A_2,...,A_n>$，矩阵$A_i$的规模为$p_{i-1} × p_i (1 \leq i \leq n)$，求完全括号化方案，使得乘积$A_1A_2...A_n$所需标量乘法次数最少。

完全括号化（fully parenthesized）：它是单一矩阵，或者是两个完全括号化的矩阵乘积链的积，且已外加括号。

刻画一个最优解的结构特征和递归地定义最优解的值

假设矩阵链$A_iA_{i+1}...A_j$的第一个最优分割点为$k,i<=k<j$，$s[i][j]$ 代表矩阵$A_iA_{i+1}...A_j$的最少标量乘法次数。则：

自底向下法:

xxxxxxxxxx
BOTTOM-UP(p)
    s = array[1..n][1..n]
    t = array[1..n-1][2..n]
    for i = 1 to n
        s[i][i] = 0
    for k = 2 to n
        for i = 1 to n - k + 1
            j = k + i - 1
            s[i][j] = Inf
            for m = i to j-1
                q = s[i][m] + s[m+1][j] + p[i_1]p[m]p[j]
                if s[i][j] >  q
                    s[i][j] = q
                    t[i][j] = m
    return s and t

最优子结构

如果一个问题的最优解包含其子问题的最优解，我们就称此问题具有最优子结构性质。

通用模式：

1. 证明问题最优解的第一个组成部分是做出一个选择，例如，选择钢条第一次切割位置，选择矩阵链的划分位置等。做出这次选会产生一个或多个待解的子问题
2. 对于一个给定问题，在其可能的第一步选择中，你假定已经知道哪种选择才会得到最优解。你现在并不关心这种选择具体是如何得到的，只是假定已经知道了这种选择
3. 给定可获得最优解的选择后，你确定这次选择会产生哪些子问题，以及如何最好地刻画子问题空间
4. 利用“剪切-粘贴”(cut-and-paste)技术证明：作为构成原问题最优解的组成部分，每个子问题的解就是它本身的最优解。

一个刻画子问题空间的好经验是：保持子问题空间尽可能简单，只在必要时扩展它。

重叠子问题

适合用动态规划方法求解的最优化问题应该具备的第二个性质是子问题空间必须足够小，即问题的递归算法会反复求解相同的子问题，而不是一直生成新的子问题。一般来说不同的子问题的总数是输入规模的多项式函数为好。

如果递归算法反复求解相同的子问题，我们就称最优化问题具有重叠子问题（overlapping subproblems）性质

与之相对的是分治方法求解的问题通常在递归的每一步都生成全新的子问题。

最长公共子序列

问题：给定两个序列$X=<x_1,x_2,...,x_m>$和$Y=<y_1,y_2,...,y_n>$，求X和Y长度最长的公共子序列

1.刻画最长公共子序列的特征

如果用暴力搜索求解LCS问题，就要穷举X的所有子序列，对每个子序列检查是否是Y的子序列，然后再记录最长的子序列。X的子序列有$2^m$个，因此暴力搜索的运行时间也是指数阶。

定理：（LCS的最优子结构）令$X=<x_1,x_2,...,x_m>$和$Y=<y_1,y_2,...,y_n>$为两个序列，$X=<x_1,x_2,...,x_m>$和$Z=<z_1,z_2,...,z_k>$为X和Y的任意LCS

1. 如果$x_m = y_n$，则$z_k = x_m = y_n$且$Z_{k-1}$是$X_{m-1}$和$Y_{n-1}$的一个LCS
2. 如果$x_m \neq y_n$，那么$z_k \neq x_m$，意味着$Z_k$是$X_{m-1}$和$Y_n$的一个LCS
3. 如果$x_m \neq y_n$，那么$z_k \neq y_n$，意味着$Z_k$是$X_{m}$和$Y_{n-1}$的一个LCS

2.递归解

由定理可知，在求X和Y的一个LCS时，我们需要求解一个或两个子问题。

我们定义$c[i,j]$表示$X_i$和$Y_j$的LCS的长度，则：

3.计算LCS的长度

xxxxxxxxxx
LCS-LENGTH(X,Y)
    m = X.length
    n = Y.length
    b = array[1..m,1..n]
    c = array[0..m,0..n]
    for i = 0 to m
        c[i,0] = 0
    for j = 1 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 b and c

4.构造LCS

我们可以用表b快速构造LCS，只需要从b[m,n]开始，并按照箭头的方向追溯下去

xxxxxxxxxx
PRINT-LCS(b,X,i,j)
    while i > 0 and j > 0
        if b[i,j] = "\"
            print X[i]
            i = i - 1
            j = j - 1
        elif b[i,j] = "|"
            i = i - 1
        else
            j = j - 1

算法改进

在此问题上，我们完全可以去掉表b，只需要表c就能回溯出LCS