動(dòng)態(tài)規(guī)劃

動(dòng)態(tài)規(guī)劃算法见转， Dynamic Programming簡(jiǎn)稱DP院刁，通程蚴荆基于一個(gè)遞推公式及一個(gè)或多個(gè)初始狀態(tài)。 當(dāng)前子問(wèn)題的解將由上一次子問(wèn)題的解推出过吻。使用動(dòng)態(tài)規(guī)劃來(lái)解題只需要多項(xiàng)式時(shí)間復(fù)雜度进泼， 因此它比回溯法、暴力法等要快許多。

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

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

硬幣問(wèn)題

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

好了，讓我們從最小的i開始吧惭嚣。當(dāng)i=0，即我們需要多少個(gè)硬幣來(lái)湊夠0元悔政。 由于1晚吞，3，5都大于0谋国，即沒有比0小的幣值槽地，因此湊夠0元我們最少需要0個(gè)硬幣。 (這個(gè)分析很傻是不是？別著急捌蚊，這個(gè)思路有利于我們理清動(dòng)態(tài)規(guī)劃究竟在做些什么集畅。) 這時(shí)候我們發(fā)現(xiàn)用一個(gè)標(biāo)記來(lái)表示這句“湊夠0元我們最少需要0個(gè)硬幣∶逶悖”會(huì)比較方便挺智， 如果一直用純文字來(lái)表述，不出一會(huì)兒你就會(huì)覺得很繞了窗宦。那么赦颇， 我們用d(i)=j來(lái)表示湊夠i元最少需要j個(gè)硬幣。于是我們已經(jīng)得到了d(0)=0赴涵， 表示湊夠0元最小需要0個(gè)硬幣媒怯。當(dāng)i=1時(shí)，只有面值為1元的硬幣可用髓窜， 因此我們拿起一個(gè)面值為1的硬幣扇苞，接下來(lái)只需要湊夠0元即可，而這個(gè)是已經(jīng)知道答案的寄纵， 即d(0)=0鳖敷。所以，d(1)=d(1-1)+1=d(0)+1=0+1=1擂啥。當(dāng)i=2時(shí)哄陶， 仍然只有面值為1的硬幣可用，于是我拿起一個(gè)面值為1的硬幣哺壶， 接下來(lái)我只需要再湊夠2-1=1元即可(記得要用最小的硬幣數(shù)量)屋吨，而這個(gè)答案也已經(jīng)知道了。 所以d(2)=d(2-1)+1=d(1)+1=1+1=2山宾。一直到這里至扰，你都可能會(huì)覺得，好無(wú)聊资锰， 感覺像做小學(xué)生的題目似的敢课。因?yàn)槲覀円恢倍贾荒懿僮髅嬷禐?的硬幣！耐心點(diǎn)绷杜， 讓我們看看i=3時(shí)的情況直秆。當(dāng)i=3時(shí)，我們能用的硬幣就有兩種了：1元的和3元的( 5元的仍然沒用鞭盟，因?yàn)槟阈枰獪惖臄?shù)目是3元圾结！5元太多了親)。 既然能用的硬幣有兩種齿诉，我就有兩種方案筝野。如果我拿了一個(gè)1元的硬幣晌姚，我的目標(biāo)就變?yōu)榱耍?湊夠3-1=2元需要的最少硬幣數(shù)量。即d(3)=d(3-1)+1=d(2)+1=2+1=3歇竟。 這個(gè)方案說(shuō)的是挥唠，我拿3個(gè)1元的硬幣；第二種方案是我拿起一個(gè)3元的硬幣焕议， 我的目標(biāo)就變成：湊夠3-3=0元需要的最少硬幣數(shù)量宝磨。即d(3)=d(3-3)+1=d(0)+1=0+1=1. 這個(gè)方案說(shuō)的是，我拿1個(gè)3元的硬幣号坡。好了懊烤，這兩種方案哪種更優(yōu)呢？ 記得我們可是要用最少的硬幣數(shù)量來(lái)湊夠3元的宽堆。所以腌紧， 選擇d(3)=1，怎么來(lái)的呢畜隶？具體是這樣得到的：d(3)=min{d(3-1)+1, d(3-3)+1}壁肋。

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

上文中d(i)表示湊夠i元需要的最少硬幣數(shù)量跛锌，我們將它定義為該問(wèn)題的”狀態(tài)”， 這個(gè)狀態(tài)是怎么找出來(lái)的呢届惋？根據(jù)子問(wèn)題定義狀態(tài)髓帽。你找到子問(wèn)題，狀態(tài)也就浮出水面了脑豹。 最終我們要求解的問(wèn)題郑藏，可以用這個(gè)狀態(tài)來(lái)表示：d(11)，即湊夠11元最少需要多少個(gè)硬幣瘩欺。 那狀態(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}歌粥。沒錯(cuò)， 它就是狀態(tài)轉(zhuǎn)移方程拍埠，描述狀態(tài)之間是如何轉(zhuǎn)移的阁吝。當(dāng)然，我們要對(duì)它抽象一下械拍，

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

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

static void get() {
    int[] dp = new int[12];//狀態(tài)表示，用d(i)=j來(lái)表示湊夠i元最少需要j個(gè)硬幣
    int inf = 100; //表示無(wú)效值迄损，這里可以取一個(gè)很大的值
    //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));
}

最長(zhǎng)非降子序列的長(zhǎng)度

一個(gè)序列有N個(gè)數(shù)：A[1],A[2],…,A[N]定躏，求出最長(zhǎng)非降子序列的長(zhǎng)度。 (講DP基本都會(huì)講到的一個(gè)問(wèn)題LIS：longest increasing subsequence)

讓我們沿用“入門”一節(jié)里那道簡(jiǎn)單題的思路來(lái)一步步找到“狀態(tài)”和“狀態(tài)轉(zhuǎn)移方程”芹敌。 假如我們考慮求A[1],A[2],…,A[i]的最長(zhǎng)非降子序列的長(zhǎng)度痊远，其中i<N， 那么上面的問(wèn)題變成了原問(wèn)題的一個(gè)子問(wèn)題(問(wèn)題規(guī)模變小了氏捞，你可以讓i=1,2,3等來(lái)分析) 然后我們定義d(i)碧聪，表示前i個(gè)數(shù)中以A[i]結(jié)尾的最長(zhǎng)非降子序列的長(zhǎng)度。OK液茎， 對(duì)照“入門”中的簡(jiǎn)單題逞姿，你應(yīng)該可以估計(jì)到這個(gè)d(i)就是我們要找的狀態(tài)。 如果我們把d(1)到d(N)都計(jì)算出來(lái)捆等，那么最終我們要找的答案就是這里面最大的那個(gè)滞造。 狀態(tài)找到了，下一步找出狀態(tài)轉(zhuǎn)移方程栋烤。
為了方便理解我們是如何找到狀態(tài)轉(zhuǎn)移方程的谒养，我先把下面的例子提到前面來(lái)講。 如果我們要求的這N個(gè)數(shù)的序列是：
5明郭，3买窟，4，8达址，6蔑祟，7
根據(jù)上面找到的狀態(tài)，我們可以得到：（下文的最長(zhǎng)非降子序列都用LIS表示）
? 前1個(gè)數(shù)的LIS長(zhǎng)度d(1)=1(序列：5)
? 前2個(gè)數(shù)的LIS長(zhǎng)度d(2)=1(序列：3沉唠；3前面沒有比3小的)
? 前3個(gè)數(shù)的LIS長(zhǎng)度d(3)=2(序列：3疆虚，4；4前面有個(gè)比它小的3满葛，所以d(3)=d(2)+1)
? 前4個(gè)數(shù)的LIS長(zhǎng)度d(4)=3(序列：3径簿，4，8嘀韧；8前面比它小的有3個(gè)數(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前面的各個(gè)子序列中哑芹，最后一個(gè)數(shù)不大于A[i]的序列長(zhǎng)度加1，然后取出最大的長(zhǎng)度即為d(i)捕透。 當(dāng)然了聪姿，有可能i前面的各個(gè)子序列中最后一個(gè)數(shù)都大于A[i]，那么d(i)=1乙嘀， 即它自身成為一個(gè)長(zhǎng)度為1的子序列末购。

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

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

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

二維的DP問(wèn)題

平面上有N*M個(gè)格子嘉冒，每個(gè)格子中放著一定數(shù)量的蘋果曹货。你從左上角的格子開始， 每一步只能向下走或是向右走讳推，每次走到一個(gè)格子上就把格子里的蘋果收集起來(lái)顶籽，這樣下去，你最多能收集到多少個(gè)蘋果银觅？
解這個(gè)問(wèn)題與解其它的DP問(wèn)題幾乎沒有什么兩樣礼饱。第一步找到問(wèn)題的“狀態(tài)”， 第二步找到“狀態(tài)轉(zhuǎn)移方程”究驴，然后基本上問(wèn)題就解決了镊绪。
首先，我們要找到這個(gè)問(wèn)題中的“狀態(tài)”是什么洒忧？我們必須注意到的一點(diǎn)是蝴韭，到達(dá)一個(gè)格子的方式最多只有兩種：從左邊來(lái)的(除了第一列)和從上邊來(lái)的(除了第一行)。 因此為了求出到達(dá)當(dāng)前格子后最多能收集到多少個(gè)蘋果熙侍，我們就要先去考察那些能到達(dá)當(dāng)前這個(gè)格子的格子榄鉴，到達(dá)它們最多能收集到多少個(gè)蘋果。 (是不是有點(diǎn)繞蛉抓，但這句話的本質(zhì)其實(shí)是DP的關(guān)鍵：欲求問(wèn)題的解庆尘，先要去求子問(wèn)題的解)
經(jīng)過(guò)上面的分析，很容易可以得出問(wèn)題的狀態(tài)和狀態(tài)轉(zhuǎn)移方程巷送。狀態(tài)S[i][j]表示我們走到(i, j)這個(gè)格子時(shí)驶忌，最多能收集到多少個(gè)蘋果。那么笑跛，狀態(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]有兩種計(jì)算方式：1.對(duì)于每一行杨刨，從左向右計(jì)算，然后從上到下逐行處理擦剑；2. 對(duì)于每一列，從上到下計(jì)算芥颈，然后從左向右逐列處理惠勒。 這樣做的目的是為了在計(jì)算S[i][j]時(shí)，S[i-1][j]和S[i][j-1]都已經(jīng)計(jì)算出來(lái)了爬坑。
代碼如下：

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í)最多可得到的蘋果數(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();
        }
    }

}

背包問(wèn)題

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

OK哥攘，如果是你，你會(huì)怎么做材鹦？你斬釘截鐵的說(shuō)：動(dòng)態(tài)規(guī)劃笆叛汀！恭喜你桶唐，答對(duì)了栅葡。 那么讓我們來(lái)看看，動(dòng)態(tài)規(guī)劃中最最最重要的兩個(gè)概念： 狀態(tài)和狀態(tài)轉(zhuǎn)移方程在這個(gè)問(wèn)題中分別是什么尤泽。
我們要怎樣去定義狀態(tài)呢欣簇？這個(gè)狀態(tài)總不能是憑空想象或是從天上掉下來(lái)的吧。 為了方便說(shuō)明安吁，讓我們先實(shí)例化上面的問(wèn)題醉蚁。一般遇到n，你就果斷地給n賦予一個(gè)很小的數(shù)鬼店， 比如n=3网棍。然后設(shè)背包容量C=10，三個(gè)寶石的體積為5妇智，4滥玷，3氏身，對(duì)應(yīng)的價(jià)值為20，10惑畴，12蛋欣。 對(duì)于這個(gè)例子，我想智商大于0的人都知道正解應(yīng)該是把體積為5和3的寶石裝到背包里如贷， 此時(shí)對(duì)應(yīng)的價(jià)值是20+12=32陷虎。接下來(lái)，我們把第三個(gè)寶石拿走杠袱， 同時(shí)背包容量減去第三個(gè)寶石的體積（因?yàn)樗茄b入背包的寶石之一）尚猿， 于是問(wèn)題的各參數(shù)變?yōu)椋簄=2，C=7楣富，體積｛5凿掂，4｝，價(jià)值｛20纹蝴，10｝庄萎。好了， 現(xiàn)在這個(gè)問(wèn)題的解是什么塘安？我想智商等于0的也解得出了：把體積為5的寶石放入背包 （然后剩下體積2糠涛，裝不下第二個(gè)寶石，只能眼睜睜看著它溜走）耙旦，此時(shí)價(jià)值為20脱羡。 這樣一來(lái)，我們發(fā)現(xiàn)免都，n=3時(shí)锉罐，放入背包的是0號(hào)和2號(hào)寶石；當(dāng)n=2時(shí)绕娘， 我們放入的是0號(hào)寶石脓规。這并不是一個(gè)偶然，沒錯(cuò)险领， 這就是傳說(shuō)中的“全局最優(yōu)解包含局部最優(yōu)解”（n=2是n=3情況的一個(gè)局部子問(wèn)題）侨舆。 繞了那么大的圈子，你可能要問(wèn)绢陌，這都哪跟哪鞍は隆？說(shuō)好的狀態(tài)呢脐湾？說(shuō)好的狀態(tài)轉(zhuǎn)移方程呢臭笆？ 別急，它們已經(jīng)呼之欲出了。
我們?cè)侔焉厦娴睦永硪幌鲁钇獭．?dāng)n=2時(shí)鹰霍，我們要求的是前2個(gè)寶石， 裝到體積為7的背包里能達(dá)到的最大價(jià)值茵乱；當(dāng)n=3時(shí)茂洒，我們要求的是前3個(gè)寶石， 裝到體積為10的背包里能達(dá)到的最大價(jià)值瓶竭。有沒有發(fā)現(xiàn)它們其實(shí)是一個(gè)句式督勺！OK， 讓我們形式化地表示一下它們斤贰， 定義d(i,j)為前i個(gè)寶石裝到剩余體積為j的背包里能達(dá)到的最大價(jià)值玷氏。 那么上面兩句話即為：d(2, 7)和d(3, 10)。這樣看著真是爽多了腋舌， 而這兩個(gè)看著很爽的符號(hào)就是我們要找的狀態(tài)了。 即狀態(tài)d(i,j)表示前i個(gè)寶石裝到剩余體積為j的背包里能達(dá)到的最大價(jià)值渗蟹。 上面那么多的文字块饺，用一句話概括就是：根據(jù)子問(wèn)題定義狀態(tài)！你找到子問(wèn)題雌芽， 狀態(tài)也就浮出水面了授艰。而我們最終要求解的最大價(jià)值即為d(n, C)：前n個(gè)寶石 （0,1,2…,n-1）裝入剩余容量為C的背包中的最大價(jià)值。狀態(tài)好不容易找到了世落， 狀態(tài)轉(zhuǎn)移方程呢淮腾？顧名思義，狀態(tài)轉(zhuǎn)移方程就是描述狀態(tài)是怎么轉(zhuǎn)移的方程（好廢話Ｌ爰选）谷朝。 那么回到例子，d(2, 7)和d(3, 10)是怎么轉(zhuǎn)移的武花？來(lái)圆凰，我們來(lái)說(shuō)說(shuō)2號(hào)寶石 （記住寶石編號(hào)是從0開始的）。從d(2, 7)到d(3, 10)就隔了這個(gè)2號(hào)寶石体箕。 它有兩種情況专钉，裝或者不裝入背包。如果裝入累铅，在面對(duì)前2個(gè)寶石時(shí)跃须，背包就只剩下體積7來(lái)裝它們，而相應(yīng)的要加上2號(hào)寶石的價(jià)值12娃兽， d(3, 10)=d(2, 10-3)+12=d(2, 7)+12菇民；如果不裝入，體積仍為10，價(jià)值自然不變了玉雾， d(3, 10)=d(2, 10)翔试。記住，d(3, 10)表示的是前3個(gè)寶石裝入到剩余體積為10 的背包里能達(dá)到的最大價(jià)值复旬，既然是最大價(jià)值垦缅，就有d(3, 10)=max{ d(2, 10), d(2, 7)+12 }。好了驹碍，這條方程描述了狀態(tài)d(i, j)的一些關(guān)系壁涎， 沒錯(cuò)，它就是狀態(tài)轉(zhuǎn)移方程了志秃。把它形式化一下：d(i, j)=max{ d(i-1, j), d(i-1,j-V[i-1]) + W[i-1] }怔球。注意討論前i個(gè)寶石裝入背包的時(shí)候， 其實(shí)是在考查第i-1個(gè)寶石裝不裝入背包（因?yàn)閷毷菑?開始編號(hào)的）浮还。至此竟坛， 狀態(tài)和狀態(tài)轉(zhuǎn)移方程都已經(jīng)有了。接下來(lái)钧舌，直接上代碼担汤。

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個(gè)寶石裝入剩余體積為j的背包中所能獲取的最大價(jià)值
        //狀態(tài)轉(zhuǎn)移方程為：vs[i]第i個(gè)寶石的體積，ws[i]第i個(gè)寶石的價(jià)值
        //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)裝入價(jià)值最多的寶石
        int column = bagVolume;

        for (int i=0; i<=row; i++) {
            for (int j=0; j<=bagVolume; j++) {
                //初始化第一行
                if (i == 0) {//前0個(gè)寶石崭歧，自然為0
                    dp[i][j] = 0;
                    continue;
                }
                //當(dāng)前背包剩余體積可以裝下第i個(gè)寶石。
                //vs[i-1]表示第i個(gè)寶石的體積撞牢，下標(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();
    }

}

好率碾，至此我們解決了背包問(wèn)題中最基本的0/1背包問(wèn)題。等等屋彪，這時(shí)你可能要問(wèn)所宰， 我現(xiàn)在只知道背包能裝入寶石的最大價(jià)值，但我還不知道要往背包里裝入哪些寶石啊畜挥。嗯歧匈， 好問(wèn)題！讓我們先定義一個(gè)數(shù)組x砰嘁，對(duì)于其中的元素為1時(shí)表示對(duì)應(yīng)編號(hào)的寶石放入背包件炉， 為0則不放入。讓我們回到上面的例子矮湘，對(duì)于體積為5斟冕，4，3缅阳，價(jià)值為20磕蛇，10景描，12的3個(gè)寶石 ，如何求得其對(duì)應(yīng)的數(shù)組x呢秀撇？（明顯我們目測(cè)一下就知道x={1 0 1}超棺， 但程序可目測(cè)不出來(lái)）OK，讓我們還是從狀態(tài)說(shuō)起呵燕。如果我們把2號(hào)寶石放入了背包棠绘， 那么是不是也就意味著，前3個(gè)寶石放入背包的最大價(jià)值要比前2個(gè)寶石放入背包的價(jià)值大再扭， 即：d(3, 10)>d(2, 10)氧苍。再用字母代替具體的數(shù)字 （不知不覺中我們就用了不完全歸納法哈），當(dāng)d(i, j)>d(i-1, j)時(shí)泛范，x(i-1)=1;OK让虐，代碼如上。

利用DP求最長(zhǎng)公共子序列

/** 
 * 返回X[0...m-1]和Y[0...n-1]的LCS的長(zhǎng)度  
 */  
static int lcs(String X, String Y, int m, int n)  
{  
    // 動(dòng)態(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é)尾的子序列的對(duì)應(yīng)的LCS長(zhǎng)度    
  
    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];  
}