算法导论笔记动态规划DP详解-钢条切割的分析与实现

摘要：假定出售一段长度为英寸的钢条的价格为单位，钢条长度均为整英寸。注若长度为英寸的钢条的价格足够大，最优解可能就是完全不需要切割。考虑长度为的情况，下图给出了英寸钢条的所有切割方案。

都是通过组合子问题的解来求解原问题。

DP中的“programming”指的是一种表格法，而非coding。

分治步骤：（例如归并排序）

将问题划分为互不相交的子问题

递归地求解子问题

组合子问题的解，求出原问题的解

对于DP：

应用于子问题重叠的情况，即不同的子问题具有公共的子子问题（子问题的求解是递归进行的，将其划分为更小的子子问题）

这种情况下分治会做很多不必要的工作，会反复求解哪些公共子问题。

而DP对每个子子问题只求解一次，将其解保存在一个表格中，无需每次都重新计算，避免重复工作。

DP通常用来求解最优化问题（optimization problem）

这种问题可以有很多可行的解，每个解都有一个值，希望找到最优值（最大或最小）的解。称这样的解为问题的一个最优解（an optimal solution）,而不是最优解（the optimal solution）,因为可能有多个解都达到最优。

刻画一个最优解的结构特征。

递归地定义最优解的值。

计算最优解的值，通常采用自底向上法。

利用计算出的信息构造一个最优解。

前三步是DP求解的基础。若仅需要一个最优解的值，而非解本身，可忽略第四步。若需第四步，有时需在执行第3步的过程中维护一些额外的信息，以便构造一个最优解。

场景：把长钢条切割为短钢条出售。切割工序本身无成本。求最佳切割方案。

假定：出售一段长度为 i 英寸的钢条的价格为Pi(i = 1, 2, …, )单位:$，钢条长度均为整英寸。下图为价格表。

问题描述：给定一段长度为n英寸的钢条和一个价格表，求切割方案，使销售收益Rn最大。注：若长度为n英寸的钢条的价格Pn足够大，最优解可能就是完全不需要切割。

考虑长度为4的情况，下图给出了4英寸钢条的所有切割方案。

切成两段各长2英寸的钢条，将产生P2 + P2 = 5 + 5 = 10 的收益，为最优解。

长度为n英寸的钢条共有2^(n-1)种不同切割方案，因为在距离钢条左端 i (i=1, 2, … , n-1)英寸处，总是可以选择切割或者不切割。用普通的加法符号表示切割方案，因此7=2+2+3表示将长度为7的钢条切割为3段：2英寸，2英寸，3英寸。

若一个最优解将钢条切割为k段（1≤k≤n），那么最优切割方案 n = i1 + i2 + … + ik.

将钢条切割为长度分别为i1, i2, … , ik的小段，得到的最大收益为 Rn = Pi1 + Pi2+…+Pik

对于上面表格的价格样例，可以观察所有最优收益值Ri (i: 1~10)以及最优方案：

长度为1：切割方案1=1（无切割）。最大收益R1 = 1

长度为2：切割方案2=2（收益5），1+1=2（收益2）。最大收益R2 = 5

长度为3：切割方案3=3（收益8），1+2=3（收益6），2+1=3（收益6）。最大收益8

长度为4：切割方案4=4（收益9），1+3=4（收益9），2+2=4（收益10），3+1=4（收益9），1+1+2=4（收益7），1+2+1=4（收益7），2+1+1=4（收益7），1+1+1+1=4（收益4）。最大收益10

长度为5：切割方案5=5（10），1+4=5（10），2+3=5（13），1+1+3=5（10），2+2+1=5（11），1+1+1+1+1=5（5），其他是前面的排列。最大收益13

依次求出。。。

更一般的，对于Rn(n≥1)，可以用更短的钢条的最优切割收益来描述它：

Rn = max(Pn, R1+Rn-1, R2 + Rn-2, … , Rn-1 + R1)

第一个参数Pn对应不切割，直接出售长度为n的方案。

其他n-1个参数对应n-1种方案。对每个i=1,2,….,n-1，将钢条切割为长度为i和n-i的两段，接着求解这两段的最优切割收益Ri和Rn-i;(每种方案的最优收益为两段的最优收益之和)。

由于无法预知哪种方案会获得最优收益，必须考察所有可能的 i ，选取其中收益最大者。若不切割时收益最大，当然选择不切割。

注意到：

为了求解规模为n的原问题，先求解子问题（子问题形式完全一样，但规模更小）。

即首次完成切割后，将两段钢条看成两个独立的钢条切割问题实例。

通过组合两个相关子问题的最优解，并在所有可能的两段切割方案中获取收益最大者，构成原问题的最优解。

称钢条切割问题满足最优子结构性质：

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

除上述解法，问题可化简为一种相似的递归：从左边切割下长度为 i 的一段，只对右边剩下的长度为 n-i 的一段进行继续切割（递归求解），对左边一段则不再进行切割。

即问题分解的方式为：将长度为n的钢条分解为左边开始一段，以及剩余部分继续分解的结果。（这样，不做任何切割的方案可以描述为：第一段长度为n，收益为Pn，剩余部分长度为0，对应收益为R0 = 0）。于是得到上面公式的简化版本：

在此公式中，原问题的最优解只包含一个相关子问题（右端剩余部分的解），而不是两个。

自顶向下递归实现的伪代码：Cut-Rod(p, n)

Cut-Rod(p, n)
1    if n==0
2        return 0
3    q = -∞
4    for i = 1 to n
5        q = max(q, p[i] + Cut-Rod(p, n-i))
6    return q

该过程以价格数组p[1...n]和整数n为输入，返回长度为n的钢条的最大收益。

若n=0，不可能有任何收益，所以第二行返回0.

第3行将最大收益初始化为负无穷，以便第4第5行的for循环能正确计算。

第6行返回结果。Java实现如下：

/**
 * 钢条切割
 */
public class CutRob {
    public static int[] prices = {1,5,8,9,10,17,17,20,24,30};
    public static int solution(int length){
        if(length == 0)    return 0;
        int result = Integer.MIN_VALUE;
        for(int i = 1; i <= length; i++){
            result = Math.max(result, prices[i-1] + solution(length-i));
        }
        return result;
    }
    public static void main(String[] args) {
        for(int i=1; i<= prices.length; i++)
            System.out.println("长度为"+i+"的最大收益为："+solution(i));
    }
}

结果：

长度为1的最大收益为：1
长度为2的最大收益为：5
长度为3的最大收益为：8
长度为4的最大收益为：10
长度为5的最大收益为：13
长度为6的最大收益为：17
长度为7的最大收益为：18
长度为8的最大收益为：22
长度为9的最大收益为：25
长度为10的最大收益为：30

该递归很好理解，但是一旦规模较大，程序运行时间会暴涨，课本上说对n=40要好几分钟，很可能超过1小时，本次实验一下n=33. (假设从钢条长度超过10开始价格就一直保持在30美元)

public class CutRob {
    public static int[] prices = 
            {1,5,8,9,10,17,17,20,24,30,
            30,30,30,30,30,30,30,30,30,30,
            30,30,30,30,30,30,30,30,30,30,
            30,30,30};
//    public static int[] prices = {1,5,8,9,10,17,17,20,24,30};
    public static int solution(int length){
        if(length == 0)    return 0;
        int result = Integer.MIN_VALUE;
        for(int i = 1; i <= length; i++){
            result = Math.max(result, prices[i-1] + solution(length-i));
        }
        return result;
    }
    public static void main(String[] args) {
        long curr = System.currentTimeMillis();
        System.out.println("长度为33的最大收益为："+solution(33));
        System.out.println(System.currentTimeMillis() - curr);
    }
}

长度为33的最大收益为：98
25507

该递归计算结果用了几乎26秒。当输入长度继续增大，会消耗更长的时间。

为什么效率这么差？原因在于，CutRob反复的用相同的参数值对自身进行递归调用，即反复的求解子问题。

下图显示了n=4时的调用过程CutRob(p, n)对i=1,2,…,n调用CutRob( p,n-i )，等价于对j=0,1,…,n-1调用CutRob( p, j )，该递归展开时，所做的工作量会爆炸性增长。

为了分析该算法运行时间，令T(n)表示第二个参数值为n时函数的调用次数。此值等于递归调用树中 根为n的子树中的节点总数，注意，此值包含了根节点对应的最初的一次调用。因此T(0)=1,且

第一项 ’1’ 表示函数的第一次调用（递归调用树的根节点），T( j )为调用cutrob(p, n-i)所产生的所有调用次数。T(n) = 2^n。即该算法的运行时间为n的指数函数。

回头看下，该运行时间并不令人惊讶。对于长度为n的钢条，该算法显然考察了所有2^(n-1)种可能的切割方案。递归调用树中共有2^(n-1)个叶子节点，每个叶子节点对应一种可能的切割方案。对每条从根到叶子的路径，路径上的标号给出了每次切割前右边剩余部分的长度（子问题规模）。也就是说，标号给出了对应的切割点（从钢条右端测量）。

看完了递归解法以及其暴涨的复杂度。下面来看下用DP怎么来解决钢条切个问题。思想如下：

已经看到，朴素递归算法之所以效率低，是因为反复求解相同的子问题。

DP会仔细安排求解顺序，对每个子问题只求解一次，并将结果保存下来。如果随后再次需要次子问题的解，只需查找保存的结果，而不必重新计算。

因此DP用空间来节省时间。是典型的时空权衡例子（time-memory trade-off）。

如果子问题数量是输入规模的多项式函数，则可以在多项式时间内求解出每个子问题。其总时间复杂度就是多项式阶的。

DP有两种等价的实现方法：带备忘的自顶向下法（top-down with memoization）& 自底向上法（bottom-up method）。

此方法仍然按照自然的递归形式编写过程，但是过程会保存每个子问题的解（通常保存在一个数组或散列表中）。

当需要一个子问题的解时，过程首先检查是否已经保存过此解，

如果是，则直接返回保存的值，从而节省了计算时间；

否则，按照通常方式计算这个子问题。

该方法一般需要恰当定义子问题“规模”的概念，使得任何子问题的求解都只依赖于“更小的”子问题的求解。

因而可以将子问题按规模排序，按由小到大的顺序进行求解。

当求解某个子问题时，所依赖的那些更小的子问题都已经求解完毕，结果已经保存。

每个子问题只求解一次，当求解它时（也是第一次遇到它），所有前提子问题都已经求解完成。

两种方法得到的算法具有相同的渐进运行时间，

仅有的差异是在某些特殊情况下，自顶向下方法并未真正递归地考察所有可能的子问题。

由于没有频繁的递归调用开销，自底向上的复杂度函数通常具有更小的系数。

mem-cut-rod(p, n)
1    let r[0…n] be a new array
2    for i=0 to n
3        r[i] = -∞
4    return mem-cut-rod-aux(p, n, r)

mem-cut-rod-aux(p, n, r)
1    if r[n] >= 0
2        return r[n]
3    if n == 0
4        q = 0
5    else 
6        q = -∞
7        for i=1 to n
8            q = max(q, p[i] + mem-cut-rod-aux(p, n-i, r))
9    r[n] = q
10   return q

主过程 mem-cut-rod(p, n)将辅助数组r[0...n]初始化为负无穷，然后调用辅助过程mem-cut-rod-aux(最初cut-rob引入备忘机制的版本)。伪代码解读：

首先检查所需值是否已知（第1行）;
如果是，则第2行直接返回保存的值;
否则第3~8行用通常方法计算所需值q;
第9行将q存入r[n]中;
第10行返回;

bottom-up-cut-rod(p, n)
1    let r[0…n] be a new array
2    r[0] = 0
3    for j=1 to n
4        q = -∞
5        for i=1 to j
6            q = max(q, p[i] + r[j-i])
7        r[j] = q
8    return r[n]

自底向上版本采用子问题的自然顺序：若i

第1行创建一个新数组r[0...n]来保存子问题的解；
第2行将r[0]初始化为0，因为长度为0的钢条没有收益；
第3~6行对j=1...n按升序求解每个规模为j的子问题。求解方法与cut-rod采用的方法相同，只是现在直接访问数组元素r[j-i]来获取规模为j-i的子问题的解，而不必进行递归调用；
第7行将规模为 j 的子问题的解存入r[j]；
第8行返回r[n],即最优解

两种方法具有相同的渐进运行时间。

bottom-up-cut-rod 主体是嵌套的双层循环，内层循环（5~6行）的迭代次数构成一个等差数列和，不难分析时间为n^2.

mem-cut-rod 运行时间也是n^2，其分析略难：当求解一个之前已经计算出结果的子问题时，递归调用会立即返回，即每个子问题只求解一次，而它求解了规模为0，1，。。。，n的子问题；为求解规模为n的子问题，第6~7行的循环会迭代n次；因此进行的所有递归调用执行此for循环的迭代次数也是一个等差数列，其和也是n^2。

public class CutRob {
    public static int[] prices = {1,5,8,9,10,17,17,20,24,30};    
    /** 自顶向下*/
    public static int mem_cut_rod(int n){
        int[] dp = new int[n+1];            // 辅助数组dp
        Arrays.fill(dp, Integer.MIN_VALUE);  // 初始化为负无穷
        return mem_cut_rod_aux(n, dp);
    }
    /** 自顶向下法的辅助函数*/
    private static int mem_cut_rod_aux(int n, int[] dp) {
        if(dp[n] >= 0)    return dp[n]; // 如果子问题已经解过，直接返回
        int max = Integer.MIN_VALUE;
        if(n==0)    max = 0;          // 如果长度为0，则最大收益为0
        else{                        // 长度若不为0
            for(int i = 1; i<=n; i++)    // 找到最大收益
                max = Math.max(max, prices[i-1] + mem_cut_rod_aux(n-i, dp));
        }
        dp[n] = max;            // 把计算得到的最大收益存入结果
        return max;                // 返回结果
    }

    public static void main(String[] args) {
        for(int i=1; i<=prices.length; i++)
            System.out.println("长度为"+i+"的最大收益为："+mem_cut_rod(i));
    }
}


长度为1的最大收益为：1
长度为2的最大收益为：5
长度为3的最大收益为：8
长度为4的最大收益为：10
长度为5的最大收益为：13
长度为6的最大收益为：17
长度为7的最大收益为：18
长度为8的最大收益为：22
长度为9的最大收益为：25
长度为10的最大收益为：30

自底向上：

public class CutRob {
    public static int[] prices = {1,5,8,9,10,17,17,20,24,30};
        /** 自底向上法*/
    private static int bottom_up_cut_rod(int n){
        int[] dp = new int[n+1];
        dp[0] = 0;
        for(int j=1; j<=n; j++){
        int max = Integer.MIN_VALUE;
        for(int i=1; i<=j; i++){
            max = Math.max(max, prices[i-1] + dp[j-i]);
        }
        dp[j] = max;
        }
        return dp[n];
    }
    public static void main(String[] args) {
        for(int i=1; i<=prices.length; i++)
            System.out.println("长度为"+i+"的最大收益为："+bottom_up_cut_rod(i));
    }
}

下面来从运行结果的时间上做一个对比，这里拿自底向上法来和前面的递归做对比。

上面的朴素递归只把输入的n增加到33，就运行了25507毫秒。下面来看下自底向上。

public class CutRob {
    public static int[] prices = 
            {1,5,8,9,10,17,17,20,24,30,
            30,30,30,30,30,30,30,30,30,30,
            30,30,30,30,30,30,30,30,30,30,
            30,30,30,30,30,30,30,30,30,30,
            30,30,30,30,30,30,30,30,30,30,
            30,30,30};
//    public static int[] prices = {1,5,8,9,10,17,17,20,24,30};
    /** 自底向上法*/
    private static int bottom_up_cut_rod(int n){
        int[] dp = new int[n+1];
        dp[0] = 0;
        for(int j=1; j<=n; j++){
            int max = Integer.MIN_VALUE;
            for(int i=1; i<=j; i++){
                max = Math.max(max, prices[i-1] + dp[j-i]);
            }
            dp[j] = max;
        }
        return dp[n];
    }
    public static void main(String[] args) {
        long curr = System.currentTimeMillis();
        System.out.println(“长度为53的最大收益为："+bottom_up_cut_rod(53));
        System.out.println(System.currentTimeMillis() - curr);
    }
}

用自底向上把输入增加到53，整个过程也就运行了1毫秒。

输出：
长度为53的最大收益为：158
1

当思考一个DP问题时，应弄清楚所涉及的子问题以及子问题之间的依赖关系。

问题的子问题图准确的表达了这些信息。下图展示了n=4时钢条切割问题的子问题图。

它是一个有向图，每个顶点唯一对应一个子问题。

若求子问题x的最优解时需要直接用到子问题y的最优解，那么在子问题图中就会有一条从子问题x的顶点到子问题y的顶点的有向边。

例如，若自顶向下过程在求解x时需要直接递归调用自身来求解y，那么子问题图就包含从x到y的一条有向边。

可以将子问题图看做自顶向下递归调用树的“简化版”或“收缩版”，因为树中所有对应相同子问题的节点合并为图中的单一顶点，相关的所有边都从父节点指向子节点。

自底向上的DP方法处理子问题图中顶点的顺序为：对于一个给定的子问题x，在求解它之前求解邻接至它的子问题y。

用22章的术语说，自底向上动态规划算法是按“逆拓扑排序”或者“反序的拓扑排序”来处理子问题图中的顶点。

换句话说，对于任何子问题，直至它所依赖的所有子问题均已求解完成，才会求解它。

类似的，可以用22章中的术语“深搜”来描述（带备忘机制的）自顶向下动态规划算法处理子问题图的顺序。（22.3节）

子问题图G = ( V, E )的规模可以帮助我们确定DP算法的运行时间。

由于每个子问题只求解一次，因此算法运行时间等于每个子问题求解时间之和。

通常，一个子问题的求解时间与子问题图中对应顶点的度（出射边的数目）成正比，而子问题的数目等于子问题图的顶点数。

因此，DP算法运行时间与顶点和边的数量成线性关系。

前文给出的钢条切割DP算法返回最优解的收益值，并未返回解本身（一个长度列表，给出切割后每段钢条的长度）。

我们可以扩展DP算法，使之对于每个问题不仅保存最优收益值，还保存对应的切割方案。利用这些信息，就能输出最优解。

下面给出bottom-up-cut-rob的扩展版本，它对于长度为j 的钢条不仅计算最大收益值Rj, 还保存最优解对应的第一段钢条的切割长度Sj：

extended-bottom-up-cut-rod(p, n)
1    let r[0…n] and s[0…n] be new arrays
2    r[0] = 0
3    for j=1 to n
4        q = -∞
5        for i=1 to j
6            if q < p[i]+r[j-i]
7                q = p[i]+r[j-i]
8                s[j] = i
9        r[j] = q
10    return r and s 

此过程和bottom-up-cut-rob很相似，差别只是在第1行创建了数组s，并在求解规模为j的子问题时，将第一段钢条的最优切割长度i保存在s[ j ]中（第8行）。

下面的过程接受两个参数：价格表p和钢条长度n，然后调用extended-bottom-up-cut-rod来计算切割下来的每段钢条的长度s[1...n]，最后输出长度为n的钢条的完整的最优切割方案：

print-cut-rob-solution(p, n)
1    (r, s) = extended-bottom-up-cut-rod(p, n)
2    while n>0
3        print s[n]
4        n = n-s[n]

对于前文给出的钢条切割实例，extended-bottom-up-cut-rod(p, 10)会返回下面的数组：

这个表一定要根据代码逻辑亲手画一遍。体会其构建过程。

i 0 1 2 3 4 5 6 7 8 9 10
r [ i ] 0 1 5 8 10 13 17 18 22 25 30
s [ i ] 0 1 2 3 2 2 6 1 2 3 10

对此例调用print-cut-rod-solution(p,10)只会输出10，但对n=7，会输出最优方案R7切割出的两段钢条长度1和6。看看Java代码实现：

public class CutRob {
    public static int[] prices = {1,5,8,9,10,17,17,20,24,30};
    private static int[] path; 
    /** 带切割方案的自底向上扩展方案*/
    public static int extended_bottom_up_cut_rod(int n){
        int[] dp = new int[n+1];
        path = new int[n+1];
        dp[0] = 0;
        for(int j = 1; j<=n; j++){
            int max = Integer.MIN_VALUE;
            for(int i=1; i<=j; i++){
                if(max < (prices[i-1] + dp[j-i])){
                    max = prices[i-1] + dp[j-i];
                    path[j] = i;
                }
            }
            dp[j] = max;
        }
        return dp[n];
    }
    /** 得到切割方案(一个最优解)*/
    public static ArrayList getACutSolution(int n){
        ArrayList result = new ArrayList<>();
        while(n > 0){
            result.add(path[n]);
            n -= path[n];
        }
        return result;
    }
    public static void main(String[] args) {
        System.out.println("长度为7的最大收益为："+extended_bottom_up_cut_rod(7));
        System.out.println(getACutSolution(7));
    }
}

输出：
长度为7的最大收益为：18
[1, 6]

至此，对DP有了一个刚刚开始的了解。