摘要：假定出售一段長度為英寸的鋼條的價格為單位，鋼條長度均為整英寸。注若長度為英寸的鋼條的價格足夠大，最優(yōu)解可能就是完全不需要切割。考慮長度為的情況，下圖給出了英寸鋼條的所有切割方案。

都是通過組合子問題的解來求解原問題。

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

分治步驟：（例如歸并排序）

將問題劃分為互不相交的子問題

遞歸地求解子問題

組合子問題的解，求出原問題的解

對于DP：

應用于子問題重疊的情況，即不同的子問題具有公共的子子問題（子問題的求解是遞歸進行的，將其劃分為更小的子子問題）

這種情況下分治會做很多不必要的工作，會反復求解哪些公共子問題。

而DP對每個子子問題只求解一次，將其解保存在一個表格中，無需每次都重新計算，避免重復工作。

DP通常用來求解最優(yōu)化問題（optimization problem）

這種問題可以有很多可行的解，每個解都有一個值，希望找到最優(yōu)值（最大或最?。┑慕?。稱這樣的解為問題的一個最優(yōu)解（an optimal solution）,而不是最優(yōu)解（the optimal solution）,因為可能有多個解都達到最優(yōu)。

刻畫一個最優(yōu)解的結構特征。

遞歸地定義最優(yōu)解的值。

計算最優(yōu)解的值，通常采用自底向上法。

利用計算出的信息構造一個最優(yōu)解。

前三步是DP求解的基礎。若僅需要一個最優(yōu)解的值，而非解本身，可忽略第四步。若需第四步，有時需在執(zhí)行第3步的過程中維護一些額外的信息，以便構造一個最優(yōu)解。

場景：把長鋼條切割為短鋼條出售。切割工序本身無成本。求最佳切割方案。

假定：出售一段長度為 i 英寸的鋼條的價格為Pi(i = 1, 2, …, )單位:$，鋼條長度均為整英寸。下圖為價格表。

問題描述：給定一段長度為n英寸的鋼條和一個價格表，求切割方案，使銷售收益Rn最大。注：若長度為n英寸的鋼條的價格Pn足夠大，最優(yōu)解可能就是完全不需要切割。

考慮長度為4的情況，下圖給出了4英寸鋼條的所有切割方案。

切成兩段各長2英寸的鋼條，將產生P2 + P2 = 5 + 5 = 10 的收益，為最優(yōu)解。

長度為n英寸的鋼條共有2^(n-1)種不同切割方案，因為在距離鋼條左端 i (i=1, 2, … , n-1)英寸處，總是可以選擇切割或者不切割。用普通的加法符號表示切割方案，因此7=2+2+3表示將長度為7的鋼條切割為3段：2英寸，2英寸，3英寸。

若一個最優(yōu)解將鋼條切割為k段（1≤k≤n），那么最優(yōu)切割方案 n = i1 + i2 + … + ik.

將鋼條切割為長度分別為i1, i2, … , ik的小段，得到的最大收益為 Rn = Pi1 + Pi2+…+Pik

對于上面表格的價格樣例，可以觀察所有最優(yōu)收益值Ri (i: 1~10)以及最優(yōu)方案：

長度為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)，可以用更短的鋼條的最優(yōu)切割收益來描述它：

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

第一個參數(shù)Pn對應不切割，直接出售長度為n的方案。

其他n-1個參數(shù)對應n-1種方案。對每個i=1,2,….,n-1，將鋼條切割為長度為i和n-i的兩段，接著求解這兩段的最優(yōu)切割收益Ri和Rn-i;(每種方案的最優(yōu)收益為兩段的最優(yōu)收益之和)。

由于無法預知哪種方案會獲得最優(yōu)收益，必須考察所有可能的 i ，選取其中收益最大者。若不切割時收益最大，當然選擇不切割。

注意到：

為了求解規(guī)模為n的原問題，先求解子問題（子問題形式完全一樣，但規(guī)模更?。?/p>

即首次完成切割后，將兩段鋼條看成兩個獨立的鋼條切割問題實例。

通過組合兩個相關子問題的最優(yōu)解，并在所有可能的兩段切割方案中獲取收益最大者，構成原問題的最優(yōu)解。

稱鋼條切割問題滿足最優(yōu)子結構性質：

問題的最優(yōu)解由相關子問題的最優(yōu)解組合而成，而這些子問題可以獨立求解。

除上述解法，問題可化簡為一種相似的遞歸：從左邊切割下長度為 i 的一段，只對右邊剩下的長度為 n-i 的一段進行繼續(xù)切割（遞歸求解），對左邊一段則不再進行切割。

即問題分解的方式為：將長度為n的鋼條分解為左邊開始一段，以及剩余部分繼續(xù)分解的結果。（這樣，不做任何切割的方案可以描述為：第一段長度為n，收益為Pn，剩余部分長度為0，對應收益為R0 = 0）。于是得到上面公式的簡化版本：

在此公式中，原問題的最優(yōu)解只包含一個相關子問題（右端剩余部分的解），而不是兩個。

自頂向下遞歸實現(xiàn)的偽代碼：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

該過程以價格數(shù)組p[1...n]和整數(shù)n為輸入，返回長度為n的鋼條的最大收益。

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

第3行將最大收益初始化為負無窮，以便第4第5行的for循環(huán)能正確計算。

第6行返回結果。Java實現(xiàn)如下：

/**
 * 鋼條切割
 */
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

該遞歸很好理解，但是一旦規(guī)模較大，程序運行時間會暴漲，課本上說對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秒。當輸入長度繼續(xù)增大，會消耗更長的時間。

為什么效率這么差？原因在于，CutRob反復的用相同的參數(shù)值對自身進行遞歸調用，即反復的求解子問題。

下圖顯示了n=4時的調用過程CutRob(p, n)對i=1,2,…,n調用CutRob( p,n-i )，等價于對j=0,1,…,n-1調用CutRob( p, j )，該遞歸展開時，所做的工作量會爆炸性增長。

為了分析該算法運行時間，令T(n)表示第二個參數(shù)值為n時函數(shù)的調用次數(shù)。此值等于遞歸調用樹中 根為n的子樹中的節(jié)點總數(shù)，注意，此值包含了根節(jié)點對應的最初的一次調用。因此T(0)=1,且

第一項 ’1’ 表示函數(shù)的第一次調用（遞歸調用樹的根節(jié)點），T( j )為調用cutrob(p, n-i)所產生的所有調用次數(shù)。T(n) = 2^n。即該算法的運行時間為n的指數(shù)函數(shù)。

回頭看下，該運行時間并不令人驚訝。對于長度為n的鋼條，該算法顯然考察了所有2^(n-1)種可能的切割方案。遞歸調用樹中共有2^(n-1)個葉子節(jié)點，每個葉子節(jié)點對應一種可能的切割方案。對每條從根到葉子的路徑，路徑上的標號給出了每次切割前右邊剩余部分的長度（子問題規(guī)模）。也就是說，標號給出了對應的切割點（從鋼條右端測量）。

看完了遞歸解法以及其暴漲的復雜度。下面來看下用DP怎么來解決鋼條切個問題。思想如下：

已經看到，樸素遞歸算法之所以效率低，是因為反復求解相同的子問題。

DP會仔細安排求解順序，對每個子問題只求解一次，并將結果保存下來。如果隨后再次需要次子問題的解，只需查找保存的結果，而不必重新計算。

因此DP用空間來節(jié)省時間。是典型的時空權衡例子（time-memory trade-off）。

如果子問題數(shù)量是輸入規(guī)模的多項式函數(shù)，則可以在多項式時間內求解出每個子問題。其總時間復雜度就是多項式階的。

DP有兩種等價的實現(xiàn)方法：帶備忘的自頂向下法（top-down with memoization）& 自底向上法（bottom-up method）。

此方法仍然按照自然的遞歸形式編寫過程，但是過程會保存每個子問題的解（通常保存在一個數(shù)組或散列表中）。

當需要一個子問題的解時，過程首先檢查是否已經保存過此解，

如果是，則直接返回保存的值，從而節(jié)省了計算時間；

否則，按照通常方式計算這個子問題。

該方法一般需要恰當定義子問題“規(guī)?！钡母拍睿沟萌魏巫訂栴}的求解都只依賴于“更小的”子問題的求解。

因而可以將子問題按規(guī)模排序，按由小到大的順序進行求解。

當求解某個子問題時，所依賴的那些更小的子問題都已經求解完畢，結果已經保存。

每個子問題只求解一次，當求解它時（也是第一次遇到它），所有前提子問題都已經求解完成。

兩種方法得到的算法具有相同的漸進運行時間，

僅有的差異是在某些特殊情況下，自頂向下方法并未真正遞歸地考察所有可能的子問題。

由于沒有頻繁的遞歸調用開銷，自底向上的復雜度函數(shù)通常具有更小的系數(shù)。

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)將輔助數(shù)組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行創(chuàng)建一個新數(shù)組r[0...n]來保存子問題的解；
第2行將r[0]初始化為0，因為長度為0的鋼條沒有收益；
第3~6行對j=1...n按升序求解每個規(guī)模為j的子問題。求解方法與cut-rod采用的方法相同，只是現(xiàn)在直接訪問數(shù)組元素r[j-i]來獲取規(guī)模為j-i的子問題的解，而不必進行遞歸調用；
第7行將規(guī)模為 j 的子問題的解存入r[j]；
第8行返回r[n],即最優(yōu)解

兩種方法具有相同的漸進運行時間。

bottom-up-cut-rod 主體是嵌套的雙層循環(huán)，內層循環(huán)（5~6行）的迭代次數(shù)構成一個等差數(shù)列和，不難分析時間為n^2.

mem-cut-rod 運行時間也是n^2，其分析略難：當求解一個之前已經計算出結果的子問題時，遞歸調用會立即返回，即每個子問題只求解一次，而它求解了規(guī)模為0，1，。。。，n的子問題；為求解規(guī)模為n的子問題，第6~7行的循環(huán)會迭代n次；因此進行的所有遞歸調用執(zhí)行此for循環(huán)的迭代次數(shù)也是一個等差數(shù)列，其和也是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];            // 輔助數(shù)組dp
        Arrays.fill(dp, Integer.MIN_VALUE);  // 初始化為負無窮
        return mem_cut_rod_aux(n, dp);
    }
    /** 自頂向下法的輔助函數(shù)*/
    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ōu)解時需要直接用到子問題y的最優(yōu)解，那么在子問題圖中就會有一條從子問題x的頂點到子問題y的頂點的有向邊。

例如，若自頂向下過程在求解x時需要直接遞歸調用自身來求解y，那么子問題圖就包含從x到y(tǒng)的一條有向邊。

可以將子問題圖看做自頂向下遞歸調用樹的“簡化版”或“收縮版”，因為樹中所有對應相同子問題的節(jié)點合并為圖中的單一頂點，相關的所有邊都從父節(jié)點指向子節(jié)點。

自底向上的DP方法處理子問題圖中頂點的順序為：對于一個給定的子問題x，在求解它之前求解鄰接至它的子問題y。

用22章的術語說，自底向上動態(tài)規(guī)劃算法是按“逆拓撲排序”或者“反序的拓撲排序”來處理子問題圖中的頂點。

換句話說，對于任何子問題，直至它所依賴的所有子問題均已求解完成，才會求解它。

類似的，可以用22章中的術語“深搜”來描述（帶備忘機制的）自頂向下動態(tài)規(guī)劃算法處理子問題圖的順序。（22.3節(jié)）

子問題圖G = ( V, E )的規(guī)?？梢詭椭覀兇_定DP算法的運行時間。

由于每個子問題只求解一次，因此算法運行時間等于每個子問題求解時間之和。

通常，一個子問題的求解時間與子問題圖中對應頂點的度（出射邊的數(shù)目）成正比，而子問題的數(shù)目等于子問題圖的頂點數(shù)。

因此，DP算法運行時間與頂點和邊的數(shù)量成線性關系。

前文給出的鋼條切割DP算法返回最優(yōu)解的收益值，并未返回解本身（一個長度列表，給出切割后每段鋼條的長度）。

我們可以擴展DP算法，使之對于每個問題不僅保存最優(yōu)收益值，還保存對應的切割方案。利用這些信息，就能輸出最優(yōu)解。

下面給出bottom-up-cut-rob的擴展版本，它對于長度為j 的鋼條不僅計算最大收益值Rj, 還保存最優(yōu)解對應的第一段鋼條的切割長度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行創(chuàng)建了數(shù)組s，并在求解規(guī)模為j的子問題時，將第一段鋼條的最優(yōu)切割長度i保存在s[ j ]中（第8行）。

下面的過程接受兩個參數(shù)：價格表p和鋼條長度n，然后調用extended-bottom-up-cut-rod來計算切割下來的每段鋼條的長度s[1...n]，最后輸出長度為n的鋼條的完整的最優(yōu)切割方案：

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)會返回下面的數(shù)組：

這個表一定要根據(jù)代碼邏輯親手畫一遍。體會其構建過程。

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，會輸出最優(yōu)方案R7切割出的兩段鋼條長度1和6。看看Java代碼實現(xiàn)：

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];
    }
    /** 得到切割方案(一個最優(yōu)解)*/
    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有了一個剛剛開始的了解。