動態(tài)規(guī)劃

動態(tài)規(guī)劃算法， Dynamic Programming簡稱DP，通?；谝粋€遞推公式及一個或多個初始狀態(tài)。 當(dāng)前子問題的解將由上一次子問題的解推出。使用動態(tài)規(guī)劃來解題只需要多項式時間復(fù)雜度， 因此它比回溯法、暴力法等要快許多。

動態(tài)規(guī)劃常常適用于有重疊子問題和最優(yōu)子結(jié)構(gòu)性質(zhì)的問題，動態(tài)規(guī)劃方法所耗時間往往遠(yuǎn)少于樸素解法。
動態(tài)規(guī)劃背后的基本思想非常簡單。大致上，若要解一個給定問題，我們需要解其不同部分（即子問題），再合并子問題的解以得出原問題的解。

通常許多子問題非常相似，為此動態(tài)規(guī)劃法試圖僅僅解決每個子問題一次，從而減少計算量：一旦某個給定子問題的解已經(jīng)算出，則將其記憶化存儲，以便下次需要同一個子問題解之時直接查表。這種做法在重復(fù)子問題的數(shù)目關(guān)于輸入的規(guī)模呈指數(shù)增長時特別有用。

硬幣問題

通過一個例子來了解一下DP的基本原理。
如果我們有面值為1元、3元和5元的硬幣若干枚，如何用最少的硬幣湊夠11元？ (表面上這道題可以用貪心算法，但貪心算法無法保證可以求出解，比如1元換成2元的時候)
首先我們思考一個問題，如何用最少的硬幣湊夠i元(i<11)？為什么要這么問呢？ 兩個原因：1.當(dāng)我們遇到一個大問題時，總是習(xí)慣把問題的規(guī)模變小，這樣便于分析討論。 2.這個規(guī)模變小后的問題和原來的問題是同質(zhì)的，除了規(guī)模變小，其它的都是一樣的， 本質(zhì)上它還是同一個問題(規(guī)模變小后的問題其實是原問題的子問題)。

好了，讓我們從最小的i開始吧。當(dāng)i=0，即我們需要多少個硬幣來湊夠0元。 由于1，3，5都大于0，即沒有比0小的幣值，因此湊夠0元我們最少需要0個硬幣。 (這個分析很傻是不是？別著急，這個思路有利于我們理清動態(tài)規(guī)劃究竟在做些什么。) 這時候我們發(fā)現(xiàn)用一個標(biāo)記來表示這句“湊夠0元我們最少需要0個硬幣?！睍容^方便， 如果一直用純文字來表述，不出一會兒你就會覺得很繞了。那么， 我們用d(i)=j來表示湊夠i元最少需要j個硬幣。于是我們已經(jīng)得到了d(0)=0， 表示湊夠0元最小需要0個硬幣。當(dāng)i=1時，只有面值為1元的硬幣可用， 因此我們拿起一個面值為1的硬幣，接下來只需要湊夠0元即可，而這個是已經(jīng)知道答案的， 即d(0)=0。所以，d(1)=d(1-1)+1=d(0)+1=0+1=1。當(dāng)i=2時， 仍然只有面值為1的硬幣可用，于是我拿起一個面值為1的硬幣， 接下來我只需要再湊夠2-1=1元即可(記得要用最小的硬幣數(shù)量)，而這個答案也已經(jīng)知道了。 所以d(2)=d(2-1)+1=d(1)+1=1+1=2。一直到這里，你都可能會覺得，好無聊， 感覺像做小學(xué)生的題目似的。因為我們一直都只能操作面值為1的硬幣！耐心點， 讓我們看看i=3時的情況。當(dāng)i=3時，我們能用的硬幣就有兩種了：1元的和3元的( 5元的仍然沒用，因為你需要湊的數(shù)目是3元！5元太多了親)。 既然能用的硬幣有兩種，我就有兩種方案。如果我拿了一個1元的硬幣，我的目標(biāo)就變?yōu)榱耍?湊夠3-1=2元需要的最少硬幣數(shù)量。即d(3)=d(3-1)+1=d(2)+1=2+1=3。 這個方案說的是，我拿3個1元的硬幣；第二種方案是我拿起一個3元的硬幣， 我的目標(biāo)就變成：湊夠3-3=0元需要的最少硬幣數(shù)量。即d(3)=d(3-3)+1=d(0)+1=0+1=1. 這個方案說的是，我拿1個3元的硬幣。好了，這兩種方案哪種更優(yōu)呢？ 記得我們可是要用最少的硬幣數(shù)量來湊夠3元的。所以， 選擇d(3)=1，怎么來的呢？具體是這樣得到的：d(3)=min{d(3-1)+1, d(3-3)+1}。

OK，碼了這么多字講具體的東西，讓我們來點抽象的。從以上的文字中， 我們要抽出動態(tài)規(guī)劃里非常重要的兩個概念：狀態(tài)和狀態(tài)轉(zhuǎn)移方程。

上文中d(i)表示湊夠i元需要的最少硬幣數(shù)量，我們將它定義為該問題的”狀態(tài)”， 這個狀態(tài)是怎么找出來的呢？根據(jù)子問題定義狀態(tài)。你找到子問題，狀態(tài)也就浮出水面了。 最終我們要求解的問題，可以用這個狀態(tài)來表示：d(11)，即湊夠11元最少需要多少個硬幣。 那狀態(tài)轉(zhuǎn)移方程是什么呢？既然我們用d(i)表示狀態(tài)，那么狀態(tài)轉(zhuǎn)移方程自然包含d(i)， 上文中包含狀態(tài)d(i)的方程是：d(3)=min{d(3-1)+1, d(3-3)+1}。沒錯， 它就是狀態(tài)轉(zhuǎn)移方程，描述狀態(tài)之間是如何轉(zhuǎn)移的。當(dāng)然，我們要對它抽象一下，

d(i)=min{ d(i-vj)+1 }，其中i-vj >=0，vj表示第j個硬幣的面值;

有了狀態(tài)和狀態(tài)轉(zhuǎn)移方程，這個問題基本上也就解決了。
代碼如下：

static void get() {
    int[] dp = new int[12];//狀態(tài)表示，用d(i)=j來表示湊夠i元最少需要j個硬幣
    int inf = 100; //表示無效值，這里可以取一個很大的值
    //dp[0]默認(rèn)為0
    for (int i=1; i<=11; i++) {
        dp[i] = min(i-1>=0?dp[i-1]+1:inf, i-3>=0?dp[i-3]+1:inf,
                i-5>=0?dp[i-5]+1:inf);
    }//dp[11]即為所求
}

private static int min(int i, int j, int k) {
    return Math.min(i, Math.min(j, k));
}

最長非降子序列的長度

一個序列有N個數(shù)：A[1],A[2],…,A[N]，求出最長非降子序列的長度。 (講DP基本都會講到的一個問題LIS：longest increasing subsequence)

讓我們沿用“入門”一節(jié)里那道簡單題的思路來一步步找到“狀態(tài)”和“狀態(tài)轉(zhuǎn)移方程”。 假如我們考慮求A[1],A[2],…,A[i]的最長非降子序列的長度，其中i<N， 那么上面的問題變成了原問題的一個子問題(問題規(guī)模變小了，你可以讓i=1,2,3等來分析) 然后我們定義d(i)，表示前i個數(shù)中以A[i]結(jié)尾的最長非降子序列的長度。OK， 對照“入門”中的簡單題，你應(yīng)該可以估計到這個d(i)就是我們要找的狀態(tài)。 如果我們把d(1)到d(N)都計算出來，那么最終我們要找的答案就是這里面最大的那個。 狀態(tài)找到了，下一步找出狀態(tài)轉(zhuǎn)移方程。
為了方便理解我們是如何找到狀態(tài)轉(zhuǎn)移方程的，我先把下面的例子提到前面來講。 如果我們要求的這N個數(shù)的序列是：
5，3，4，8，6，7
根據(jù)上面找到的狀態(tài)，我們可以得到：（下文的最長非降子序列都用LIS表示）
? 前1個數(shù)的LIS長度d(1)=1(序列：5)
? 前2個數(shù)的LIS長度d(2)=1(序列：3；3前面沒有比3小的)
? 前3個數(shù)的LIS長度d(3)=2(序列：3，4；4前面有個比它小的3，所以d(3)=d(2)+1)
? 前4個數(shù)的LIS長度d(4)=3(序列：3，4，8；8前面比它小的有3個數(shù)，所以 d(4)=max{d(1),d(2),d(3)}+1=3)
OK，分析到這，我覺得狀態(tài)轉(zhuǎn)移方程已經(jīng)很明顯了，如果我們已經(jīng)求出了d(1)到d(i-1)， 那么d(i)可以用下面的狀態(tài)轉(zhuǎn)移方程得到：
d(i) = max{1, d(j)+1},其中j<i,A[j]<=A[i]
用大白話解釋就是，想要求d(i)，就把i前面的各個子序列中，最后一個數(shù)不大于A[i]的序列長度加1，然后取出最大的長度即為d(i)。 當(dāng)然了，有可能i前面的各個子序列中最后一個數(shù)都大于A[i]，那么d(i)=1， 即它自身成為一個長度為1的子序列。

實際代碼中的dp[i]表示從數(shù)組第i個下標(biāo)處值到數(shù)組起始位置的最長非降序子序列的長度。

static void get(int[] array) {
    int[] dp = new int[array.length];
    for (int i=0; i<dp.length; i++) {//初始化為1，長度至少為1
        dp[i] = 1;
    }
    
    for (int i=0; i<dp.length; i++) {//對數(shù)組中的元素遍歷，求相應(yīng)的dp[i]
        for (int k=0; k<i; k++) {//遍歷下標(biāo)i元素之前的所有元素
            if (array[k] <= array[i]) {//對小于等于array[i]嘗試求最大LIS
                dp[i] = max(dp[i], dp[k]+1);
            }
        }
    }
    
}

最后找到dp數(shù)組中的最大值即可。

二維的DP問題

平面上有N*M個格子，每個格子中放著一定數(shù)量的蘋果。你從左上角的格子開始， 每一步只能向下走或是向右走，每次走到一個格子上就把格子里的蘋果收集起來，這樣下去，你最多能收集到多少個蘋果？
解這個問題與解其它的DP問題幾乎沒有什么兩樣。第一步找到問題的“狀態(tài)”， 第二步找到“狀態(tài)轉(zhuǎn)移方程”，然后基本上問題就解決了。
首先，我們要找到這個問題中的“狀態(tài)”是什么？我們必須注意到的一點是，到達(dá)一個格子的方式最多只有兩種：從左邊來的(除了第一列)和從上邊來的(除了第一行)。 因此為了求出到達(dá)當(dāng)前格子后最多能收集到多少個蘋果，我們就要先去考察那些能到達(dá)當(dāng)前這個格子的格子，到達(dá)它們最多能收集到多少個蘋果。 (是不是有點繞，但這句話的本質(zhì)其實是DP的關(guān)鍵：欲求問題的解，先要去求子問題的解)
經(jīng)過上面的分析，很容易可以得出問題的狀態(tài)和狀態(tài)轉(zhuǎn)移方程。狀態(tài)S[i][j]表示我們走到(i, j)這個格子時，最多能收集到多少個蘋果。那么，狀態(tài)轉(zhuǎn)移方程如下：
S[i][j] = A[i][j] + max(S[i-1][j], if i>0 ; S[i][j-1], if j>0)
其中i代表行，j代表列，下標(biāo)均從0開始；A[i][j]代表格子(i, j)處的蘋果數(shù)量。
S[i][j]有兩種計算方式：1.對于每一行，從左向右計算，然后從上到下逐行處理；2. 對于每一列，從上到下計算，然后從左向右逐列處理。 這樣做的目的是為了在計算S[i][j]時，S[i-1][j]和S[i][j-1]都已經(jīng)計算出來了。
代碼如下：

public class Test01 {
    public static void main(String[] args) {
        int[][] dish = {{1,2,3,4},{5,6,7,8}};//格子中的蘋果數(shù)量
        
        int row = dish.length;
        int column = dish[0].length;
        
        int[][] dp = new int[row][column];//dp[i][j]表示走到dish[i][j]時最多可得到的蘋果數(shù)量
        
        printArray(dish);
        
        for (int i=0; i<row; i++) {
            for (int j=0; j<column; j++) {
                dp[i][j] = max(i-1>=0 ? dp[i-1][j] : 0, 
                        j-1>=0 ? dp[i][j-1] : 0) + dish[i][j];
            }
        }
        
        printArray(dp);
        System.out.println("max:"+dp[row-1][column-1]);
    }
    
    private static int max(int i, int j) {
        return i > j ? i : j;
    }

    static void printArray(int[][] ns) {
        for (int i=0; i<ns.length; i++) {
            for (int j=0; j<ns[0].length; j++) {
                System.out.print(ns[i][j] + " ");
            }
            System.out.println();
        }
    }

}

背包問題

話說有一哥們?nèi)ド掷锿姘l(fā)現(xiàn)了一堆寶石，他數(shù)了數(shù)，一共有n個。 但他身上能裝寶石的就只有一個背包，背包的容量為C。這哥們把n個寶石排成一排并編上號： 0,1,2,…,n-1。第i個寶石對應(yīng)的體積和價值分別為V[i]和W[i] 。排好后這哥們開始思考： 背包總共也就只能裝下體積為C的東西，那我要裝下哪些寶石才能讓我獲得最大的利益呢？

OK，如果是你，你會怎么做？你斬釘截鐵的說：動態(tài)規(guī)劃?。」材?，答對了。 那么讓我們來看看，動態(tài)規(guī)劃中最最最重要的兩個概念： 狀態(tài)和狀態(tài)轉(zhuǎn)移方程在這個問題中分別是什么。
我們要怎樣去定義狀態(tài)呢？這個狀態(tài)總不能是憑空想象或是從天上掉下來的吧。 為了方便說明，讓我們先實例化上面的問題。一般遇到n，你就果斷地給n賦予一個很小的數(shù)， 比如n=3。然后設(shè)背包容量C=10，三個寶石的體積為5，4，3，對應(yīng)的價值為20，10，12。 對于這個例子，我想智商大于0的人都知道正解應(yīng)該是把體積為5和3的寶石裝到背包里， 此時對應(yīng)的價值是20+12=32。接下來，我們把第三個寶石拿走， 同時背包容量減去第三個寶石的體積（因為它是裝入背包的寶石之一）， 于是問題的各參數(shù)變?yōu)椋簄=2，C=7，體積｛5，4｝，價值｛20，10｝。好了， 現(xiàn)在這個問題的解是什么？我想智商等于0的也解得出了：把體積為5的寶石放入背包 （然后剩下體積2，裝不下第二個寶石，只能眼睜睜看著它溜走），此時價值為20。 這樣一來，我們發(fā)現(xiàn)，n=3時，放入背包的是0號和2號寶石；當(dāng)n=2時， 我們放入的是0號寶石。這并不是一個偶然，沒錯， 這就是傳說中的“全局最優(yōu)解包含局部最優(yōu)解”（n=2是n=3情況的一個局部子問題）。 繞了那么大的圈子，你可能要問，這都哪跟哪??？說好的狀態(tài)呢？說好的狀態(tài)轉(zhuǎn)移方程呢？ 別急，它們已經(jīng)呼之欲出了。
我們再把上面的例子理一下。當(dāng)n=2時，我們要求的是前2個寶石， 裝到體積為7的背包里能達(dá)到的最大價值；當(dāng)n=3時，我們要求的是前3個寶石， 裝到體積為10的背包里能達(dá)到的最大價值。有沒有發(fā)現(xiàn)它們其實是一個句式！OK， 讓我們形式化地表示一下它們， 定義d(i,j)為前i個寶石裝到剩余體積為j的背包里能達(dá)到的最大價值。 那么上面兩句話即為：d(2, 7)和d(3, 10)。這樣看著真是爽多了， 而這兩個看著很爽的符號就是我們要找的狀態(tài)了。 即狀態(tài)d(i,j)表示前i個寶石裝到剩余體積為j的背包里能達(dá)到的最大價值。 上面那么多的文字，用一句話概括就是：根據(jù)子問題定義狀態(tài)！你找到子問題， 狀態(tài)也就浮出水面了。而我們最終要求解的最大價值即為d(n, C)：前n個寶石 （0,1,2…,n-1）裝入剩余容量為C的背包中的最大價值。狀態(tài)好不容易找到了， 狀態(tài)轉(zhuǎn)移方程呢？顧名思義，狀態(tài)轉(zhuǎn)移方程就是描述狀態(tài)是怎么轉(zhuǎn)移的方程（好廢話?。?那么回到例子，d(2, 7)和d(3, 10)是怎么轉(zhuǎn)移的？來，我們來說說2號寶石 （記住寶石編號是從0開始的）。從d(2, 7)到d(3, 10)就隔了這個2號寶石。 它有兩種情況，裝或者不裝入背包。如果裝入，在面對前2個寶石時，背包就只剩下體積7來裝它們，而相應(yīng)的要加上2號寶石的價值12， d(3, 10)=d(2, 10-3)+12=d(2, 7)+12；如果不裝入，體積仍為10，價值自然不變了， d(3, 10)=d(2, 10)。記住，d(3, 10)表示的是前3個寶石裝入到剩余體積為10 的背包里能達(dá)到的最大價值，既然是最大價值，就有d(3, 10)=max{ d(2, 10), d(2, 7)+12 }。好了，這條方程描述了狀態(tài)d(i, j)的一些關(guān)系， 沒錯，它就是狀態(tài)轉(zhuǎn)移方程了。把它形式化一下：d(i, j)=max{ d(i-1, j), d(i-1,j-V[i-1]) + W[i-1] }。注意討論前i個寶石裝入背包的時候， 其實是在考查第i-1個寶石裝不裝入背包（因為寶石是從0開始編號的）。至此， 狀態(tài)和狀態(tài)轉(zhuǎn)移方程都已經(jīng)有了。接下來，直接上代碼。

public class Test01 {
    public static void main(String[] args) {
        int vs[] = {5,4,3,3};//寶石體積
        int ws[] = {20,10,12,15};//寶石重量
        int bagVolume = 10;//背包體積
        
        //狀態(tài)dp[i][j]表示將前i個寶石裝入剩余體積為j的背包中所能獲取的最大價值
        //狀態(tài)轉(zhuǎn)移方程為：vs[i]第i個寶石的體積，ws[i]第i個寶石的價值
        //dp[i][j]=max{dp[i-1][j](不裝入背包),dp[i-1][j-vs[i]]+ws[i](裝入)};
        int[][] dp = new int[vs.length+1][bagVolume+1];
        int row = vs.length;
        //背包體積，要求在體積范圍內(nèi)裝入價值最多的寶石
        int column = bagVolume;

        for (int i=0; i<=row; i++) {
            for (int j=0; j<=bagVolume; j++) {
                //初始化第一行
                if (i == 0) {//前0個寶石，自然為0
                    dp[i][j] = 0;
                    continue;
                }
                //當(dāng)前背包剩余體積可以裝下第i個寶石。
                //vs[i-1]表示第i個寶石的體積，下標(biāo)從0開始
                if (j >= vs[i-1]) {
                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-vs[i-1]]+ws[i-1]);
                }
            }
        }


        System.out.println("max:"+dp[row][column]);
        
        //標(biāo)記裝入背包的寶石
        int book[] = new int[vs.length];
        int j = bagVolume;
        for (int i=vs.length; i>0; i--) {
            if (dp[i][j] > dp[i-1][j]) {
                book[i-1] = 1;
                j = j - vs[i-1];
            }
        }
        printArray(book);
    }
    
    private static int max(int i, int j) {
        // TODO Auto-generated method stub
        return i > j ? i : j;
    }


    static void printArray(int[] ns) {
        for (int i=0; i<ns.length; i++) {
            System.out.printf("%-3d ",ns[i]);
        }
        System.out.println();
    }

}

好，至此我們解決了背包問題中最基本的0/1背包問題。等等，這時你可能要問， 我現(xiàn)在只知道背包能裝入寶石的最大價值，但我還不知道要往背包里裝入哪些寶石啊。嗯， 好問題！讓我們先定義一個數(shù)組x，對于其中的元素為1時表示對應(yīng)編號的寶石放入背包， 為0則不放入。讓我們回到上面的例子，對于體積為5，4，3，價值為20，10，12的3個寶石 ，如何求得其對應(yīng)的數(shù)組x呢？（明顯我們目測一下就知道x={1 0 1}， 但程序可目測不出來）OK，讓我們還是從狀態(tài)說起。如果我們把2號寶石放入了背包， 那么是不是也就意味著，前3個寶石放入背包的最大價值要比前2個寶石放入背包的價值大， 即：d(3, 10)>d(2, 10)。再用字母代替具體的數(shù)字 （不知不覺中我們就用了不完全歸納法哈），當(dāng)d(i, j)>d(i-1, j)時，x(i-1)=1;OK，代碼如上。

利用DP求最長公共子序列

/** 
 * 返回X[0...m-1]和Y[0...n-1]的LCS的長度  
 */  
static int lcs(String X, String Y, int m, int n)  
{  
    // 動態(tài)規(guī)劃表，大小(m+1)*(n+1)  
    int[][] dp = new int[m+1][n+1];//dp[i][j]表示X[i-1]，Y[j-1]下標(biāo)為結(jié)尾的子序列的對應(yīng)的LCS長度    
  
    for(int i=0; i<m+1; ++i)  
    {  
        for(int j=0; j<n+1; ++j)  
        {  
            // 第一行和第一列置0  
            if (i == 0 || j == 0)  
                dp[i][j] = 0;  
  
            else if(X.charAt(i-1) == Y.charAt(j-1))  
                dp[i][j] = dp[i-1][j-1] + 1;  
            else  
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);  
        }  
    }  
    return table[m][n];  
}