來(lái)自公眾號(hào)：碼海

前言

動(dòng)態(tài)規(guī)劃（dynamic programming揭措，簡(jiǎn)稱 dp)是工程中非常重要的解決問(wèn)題的思想屎媳，從我們?cè)诠こ讨械貓D軟件上應(yīng)用的最短路徑問(wèn)題晴玖，再在生活中的在淘寶上如何湊單以便利用滿減券來(lái)最大程度地達(dá)到我們合理薅羊毛的目的 区岗，很多時(shí)候都能看到它的身影涛救。不過(guò)動(dòng)態(tài)規(guī)劃對(duì)初學(xué)者來(lái)說(shuō)確實(shí)比較難，dp狀態(tài)比勉，狀態(tài)轉(zhuǎn)移方程讓人摸不著頭腦劳较，網(wǎng)上很多人也反饋不太好學(xué)驹止，其實(shí)就像我們之前學(xué)遞歸那樣，任何算法的學(xué)習(xí)都是有它的規(guī)律和套路的观蜗，只要掌握好它的規(guī)律及解題的套路臊恋，再加上大量的習(xí)題練習(xí)，相信掌握它不是什么難事墓捻，本文將會(huì)用比較淺顯易懂地講解來(lái)幫助大家掌握動(dòng)態(tài)規(guī)劃這一在工程中非常重要的思想抖仅，相信看完后，動(dòng)態(tài)規(guī)劃的解題套路一定能手到擒來(lái)（文章有點(diǎn)長(zhǎng)砖第，建議先收藏再看撤卢，看完后一定會(huì)對(duì)動(dòng)態(tài)規(guī)劃的認(rèn)知上升到一個(gè)臺(tái)階！）

本文將會(huì)從以下角度來(lái)講解動(dòng)態(tài)規(guī)劃：

• 什么是動(dòng)態(tài)規(guī)劃
• 動(dòng)態(tài)規(guī)劃從入門到進(jìn)階
• 再談動(dòng)態(tài)規(guī)劃

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

以下是我綜合了動(dòng)態(tài)規(guī)劃的特點(diǎn)給出的動(dòng)態(tài)規(guī)劃的定義：動(dòng)態(tài)規(guī)劃是一種多階段決策最優(yōu)解模型梧兼，一般用來(lái)求最值問(wèn)題放吩，多數(shù)情況下它可以采用自下而上的遞推方式來(lái)得出每個(gè)子問(wèn)題的最優(yōu)解（即最優(yōu)子結(jié)構(gòu)），進(jìn)而自然而然地得出依賴子問(wèn)題的原問(wèn)題的最優(yōu)解羽杰。

劃重點(diǎn)：

1. 多階段決策渡紫，意味著問(wèn)題可以分解成子問(wèn)題，子子問(wèn)題考赛，惕澎。。颜骤。唧喉，也就是說(shuō)問(wèn)題可以拆分成多個(gè)子問(wèn)題進(jìn)行求解
2. 最優(yōu)子結(jié)構(gòu)，在自下而上的遞推過(guò)程中忍抽，我們求得的每個(gè)子問(wèn)題一定是全局最優(yōu)解八孝，既然它分解的子問(wèn)題是全局最優(yōu)解，那么依賴于它們解的原問(wèn)題自然也是全局最優(yōu)解梯找。
3. 自下而上唆阿，怎樣才能自下而上的求出每個(gè)子問(wèn)題的最優(yōu)解呢，可以肯定子問(wèn)題之間是有一定聯(lián)系的锈锤，即迭代遞推公式驯鳖，也叫「狀態(tài)轉(zhuǎn)移方程」，要定義好這個(gè)狀態(tài)轉(zhuǎn)移方程久免， 我們就需要定義好每個(gè)子問(wèn)題的狀態(tài)（DP 狀態(tài)）浅辙，那為啥要自下而上地求解呢，因?yàn)槿绻捎孟襁f歸這樣自頂向下的求解方式阎姥，子問(wèn)題之間可能存在大量的重疊记舆，大量地重疊子問(wèn)題意味著大量地重復(fù)計(jì)算，這樣時(shí)間復(fù)雜度很可能呈指數(shù)級(jí)上升（在下文中我們會(huì)看到多個(gè)這樣重復(fù)的計(jì)算導(dǎo)致的指數(shù)級(jí)的時(shí)間復(fù)雜度）呼巴，所以自下而上的求解方式可以消除重疊子問(wèn)題泽腮。

簡(jiǎn)單總結(jié)一下御蒲，最優(yōu)子結(jié)構(gòu)，狀態(tài)轉(zhuǎn)移方程诊赊，重疊子問(wèn)題就是動(dòng)態(tài)規(guī)劃的三要素厚满，這其中定義子問(wèn)題的狀態(tài)與寫(xiě)出狀態(tài)轉(zhuǎn)移方程是解決動(dòng)態(tài)規(guī)劃最為關(guān)鍵的步驟，狀態(tài)轉(zhuǎn)移方程如果定義好了碧磅，解決動(dòng)態(tài)規(guī)劃就基本不是問(wèn)題了碘箍。

既然我們知道動(dòng)態(tài)規(guī)劃的基本概念及特征，那么怎么判斷題目是否可以用動(dòng)態(tài)規(guī)劃求解呢鲸郊，其實(shí)也很簡(jiǎn)單丰榴，當(dāng)問(wèn)題的定義是求最值問(wèn)題，且問(wèn)題可以采用遞歸的方式秆撮，并且遞歸的過(guò)程中有大量重復(fù)子問(wèn)題的時(shí)候四濒，基本可以斷定問(wèn)題可以用動(dòng)態(tài)規(guī)劃求解，于是我們得出了求解動(dòng)態(tài)規(guī)劃基本思路如下（解題四步曲）

1. 判斷是否可用遞歸來(lái)解职辨，可以的話進(jìn)入步驟 2
2. 分析在遞歸的過(guò)程中是否存在大量的重復(fù)子問(wèn)題
3. 采用備忘錄的方式來(lái)存子問(wèn)題的解以避免大量的重復(fù)計(jì)算（剪枝）
4. 改用自底向上的方式來(lái)遞推峻黍，即動(dòng)態(tài)規(guī)劃

畫(huà)外音：遞歸怎么求解，強(qiáng)烈建議看下這篇文章拨匆，好評(píng)如潮,總結(jié)了常見(jiàn)的遞歸解題套路

可能不少人看了以上的動(dòng)態(tài)規(guī)劃的一些介紹還是對(duì)一些定義如 DP 狀態(tài)，狀態(tài)轉(zhuǎn)移方程挽拂，自底而上不了解惭每，沒(méi)關(guān)系 ，接下來(lái)我們會(huì)做幾道習(xí)題來(lái)強(qiáng)化一下大家對(duì)這些概念及動(dòng)態(tài)規(guī)劃解題四步曲的理解亏栈，每道題我們都會(huì)分別用遞歸台腥，遞歸+備忘錄，動(dòng)態(tài)規(guī)劃來(lái)求解一遍绒北，這樣也進(jìn)一步幫助大家來(lái)鞏固我們之前學(xué)的遞歸知識(shí)

動(dòng)態(tài)規(guī)劃從入門到進(jìn)階

入門題：斐波那契數(shù)列

接下來(lái)我們來(lái)看看怎么用動(dòng)態(tài)規(guī)劃解題四步曲來(lái)解斐波那契數(shù)列

畫(huà)外音：斐波那契數(shù)列并不是嚴(yán)格意義上的動(dòng)態(tài)規(guī)劃黎侈，因?yàn)樗簧婕暗角笞钪担眠@個(gè)例子旨在說(shuō)明重疊子問(wèn)題與狀態(tài)轉(zhuǎn)移方程

1闷游、判斷是否可用遞歸來(lái)解顯然是可以的峻汉，遞歸代碼如下

public static int fibonacci(int n) {    if (n == 1) return 1;    if (n == 2) return 2;    return fibonacci(n - 1) + fibonacci(n - 2);}

2、分析在遞歸的過(guò)程中是否存在大量的重復(fù)子問(wèn)題

怎么分析是否有重復(fù)子問(wèn)題脐往，畫(huà)出遞歸樹(shù)

image

可以看到光是求 f(6)休吠，就有兩次重復(fù)的計(jì)算， f(4) 求解了兩次业簿，f(3) 求解了兩次瘤礁，時(shí)間復(fù)雜度是指數(shù)級(jí)別，遞歸時(shí)間復(fù)雜度怎么看梅尤，解決每個(gè)子問(wèn)題需要的時(shí)間乘以子問(wèn)題總數(shù)柜思，每個(gè)子問(wèn)題需要的時(shí)間即 f(n) = f(n-1) + f(n-2) 只做了一次加法運(yùn)算岩调，子問(wèn)題的個(gè)數(shù)有多少呢，每個(gè)問(wèn)題一分為二,是個(gè)二叉樹(shù)赡盘，可以看到第一層 1 個(gè)号枕，第二層 2 個(gè)，第三層 4 個(gè)亡脑，即 1 + 2 + 2^2 + .... 2^{n堕澄，所以總的來(lái)說(shuō)時(shí)間復(fù)雜度是)O(2}n),是指數(shù)級(jí)別

畫(huà)外音：求解問(wèn)題 f(6),轉(zhuǎn)成求 f(5),f(4),從原問(wèn)題出發(fā)，分解成求子問(wèn)題霉咨，子問(wèn)題再分解成子子問(wèn)題蛙紫，。途戒。坑傅。，直到再也不能分解喷斋，這種從 原問(wèn)題展開(kāi)子問(wèn)題進(jìn)行求解的方式叫自頂向下

3唁毒、采用備忘錄的方式來(lái)存子問(wèn)題的解以避免大量的重復(fù)計(jì)算既然以上中間子問(wèn)題中存在著大量的重復(fù)計(jì)算，那么我們可以把這些中間結(jié)果給緩存仔亲Α（可以用哈希表緩存）浆西，如下

public static int fibonacci(int n) {    if (n = 1) return 1;    if (n = 2) return 2;    if (map.get(n) != null)  {        return map.get(n);    }    int result = fibonacci(n - 1) + fibonacci(n - 2);    map.put(n, result);    return result;}

這么緩存之后再看我們的遞歸樹(shù)

image

可以看到通過(guò)緩存中間的數(shù)據(jù)，做了大量地剪枝的工作顽腾，同樣的f(4),f(3),f(2)近零，都只算一遍了,省去了大量的重復(fù)計(jì)算，問(wèn)題的規(guī)模從二叉樹(shù)變成了單鏈表（即 n）抄肖，時(shí)間復(fù)雜度變成了 O(n)久信，不過(guò)由于哈希表緩存了所有的子問(wèn)題的結(jié)果，空間復(fù)雜度是 O(n)漓摩。

4裙士、改用自底向上的方式來(lái)遞推，即動(dòng)態(tài)規(guī)劃我們注意到如下規(guī)律

f(1) = 1f(2) = 2f(3) = f(1) + f(2) = 3f(4) = f(3) + f(2) = 5....f(n) = f(n-1) + f(n-2)

image

畫(huà)外音：從最終地不能再分解的子問(wèn)題根據(jù)遞推方程（f(n) = f(n-1) + f(n-2)）逐漸求它上層的問(wèn)題管毙，上上層問(wèn)題腿椎，最終求得一開(kāi)始的問(wèn)題，這種求解問(wèn)題的方式就叫自底向上锅风。

f(n) 就是定義的每個(gè)子問(wèn)題的狀態(tài)（DP 狀態(tài)）酥诽，f(n) = f(n-1) + f(n-2) 就是狀態(tài)轉(zhuǎn)移方程，即 f(n) 由 f(n-1), f(n-2) 這兩個(gè)狀態(tài)轉(zhuǎn)移而來(lái),由于每個(gè)子問(wèn)題只與它前面的兩個(gè)狀態(tài)皱埠，所以我們只要定義三個(gè)變量肮帐，自底向上不斷循環(huán)迭代即可，如下

public int f(int n) {    if (n == 1) return 1;    if (n == 2) return 2;    int result = 0;    int pre = 1;    int next = 2;        for (int i = 3; i < n + 1; i ++) {        result = pre + next;        pre = next;        next = result;    }    return result;}

這樣時(shí)間復(fù)雜度雖然還是O(n)，但空間復(fù)雜度只由于只定義了三個(gè)變量（result,pre,next）所以是常量 O(1)训枢。

通過(guò)簡(jiǎn)單地斐波那契的例子托修，相信大家對(duì)自底向上，DP 狀態(tài)恒界， DP 轉(zhuǎn)移方程應(yīng)該有了比較深入地認(rèn)識(shí)睦刃，細(xì)心的同學(xué)一定發(fā)現(xiàn)了最優(yōu)子結(jié)構(gòu)怎么沒(méi)有，因?yàn)榍懊嫖覀円舱f(shuō)了十酣，斐波那契數(shù)列并不是嚴(yán)格意義上的動(dòng)態(tài)規(guī)劃涩拙，只是先用這個(gè)簡(jiǎn)單地例子來(lái)幫助大家了解一下一些基本的概念。在之后的習(xí)題中我們將會(huì)見(jiàn)識(shí)到真正的動(dòng)態(tài)規(guī)劃

小試牛刀：三角形的最小路徑和

image

如圖示耸采，以上三角形由一連串的數(shù)字構(gòu)成兴泥，要求從頂點(diǎn) 2 開(kāi)始走到最底下邊的最短路徑，每次只能向當(dāng)前節(jié)點(diǎn)下面的兩個(gè)節(jié)點(diǎn)走虾宇，如 3 可以向 6 或 5 走搓彻，不能直接走到 7。

image

如圖示:從 2 走到最底下最短路徑為 2+3+5+1 = 11,即為我們所求的

首先我們需要用一個(gè)二維數(shù)組來(lái)表示這個(gè)三個(gè)角形的節(jié)點(diǎn)嘱朽，用二維數(shù)組顯然可以做到旭贬， 第一行的 2 用 a[0][0] 表示，第二行元素 3, 4 用 a[1][0],a[1][1],依此類推搪泳。

image

定義好數(shù)據(jù)結(jié)構(gòu)之后稀轨，接下來(lái)我們來(lái)看看如何套用我們的動(dòng)態(tài)規(guī)劃解題套路來(lái)解題

1、 判斷是否可用遞歸來(lái)解

如果用遞歸岸军，就要窮舉所有的路徑和靶端，最后再求所有路徑和的最小值，我們來(lái)看看用遞歸怎么做凛膏。

對(duì)于每個(gè)節(jié)點(diǎn)都可以走它的左或右節(jié)點(diǎn)，假設(shè)我們定義 traverse(i, j) 為節(jié)點(diǎn) a[i][j] 下一步要走的節(jié)點(diǎn)脏榆，則可以得出遞歸公式的偽代碼如下

traverse(i, j) = {    traverse(i+1, j);    向節(jié)點(diǎn)i,j 下面的左節(jié)點(diǎn)走一步    traverse(i+1, j+1);    向節(jié)點(diǎn)i,j 下面的右節(jié)點(diǎn)走一步}

什么時(shí)候終止呢猖毫，顯然是遍歷到三角形最后一條邊的節(jié)點(diǎn)時(shí)終止，發(fā)現(xiàn)了嗎须喂，對(duì)每個(gè)節(jié)點(diǎn)來(lái)說(shuō)吁断，在往下（無(wú)論是往左還是往右）遍歷的過(guò)程中，問(wèn)題規(guī)模不斷地在縮小坞生，也有臨界條件（到達(dá)最后一條邊的節(jié)點(diǎn)時(shí)終止）仔役，分解的子問(wèn)題也有相同的解決問(wèn)題的思路（對(duì)于每個(gè)節(jié)點(diǎn)的遍歷都是往左或往右），符合遞歸的條件是己！于是我們得到遞歸代碼如下

private static int[][] triangle = {            {2, 0, 0, 0},            {3, 4, 0, 0},            {6, 5, 7, 0},            {4, 1, 8, 3}};public static int traverse(int i, int j) {    int totalRow = 4; // 總行數(shù)    if (i >=  totalRow - 1) {        return 0;    }    // 往左下節(jié)點(diǎn)走時(shí)    int leftSum = traverse(i+1, j) + triangle[i+1][j];    // 往右下節(jié)點(diǎn)走時(shí)    int rightSum = traverse(i+1, j+1) + triangle[i+1][j+1];    // 記錄每個(gè)節(jié)點(diǎn)往左和往右遍歷的路徑和的最小值    return Math.min(leftSum, rightSum);}public static  void main(String[] args)  throws Throwable {    int sum = traverse(0, 0) + triangle[0][0];    System.out.println("sum = " + sum);}

時(shí)間復(fù)雜度是多少呢又兵，從以下偽代碼可以看出

traverse(i, j) = {    traverse(i+1, j);    向節(jié)點(diǎn)i,j 下面的左節(jié)點(diǎn)走一步    traverse(i+1, j+1);    向節(jié)點(diǎn)i,j 下面的右節(jié)點(diǎn)走一步}

對(duì)于每個(gè)節(jié)點(diǎn)，要么向左或向右，每個(gè)問(wèn)題都分解成了兩個(gè)子問(wèn)題沛厨，和斐波那契數(shù)列一樣宙地，如果畫(huà)出遞歸樹(shù)也是個(gè)二叉樹(shù)，所以時(shí)間復(fù)雜度是 O(2^n),也是指數(shù)級(jí)別逆皮。

2宅粥、分析在遞歸的過(guò)程中是否存在大量的重復(fù)子問(wèn)題

為啥時(shí)間復(fù)雜度是指數(shù)級(jí)別呢，我們簡(jiǎn)單分析一下：

image

對(duì)于節(jié)點(diǎn) 3 和 4 來(lái)說(shuō)电谣，如果節(jié)點(diǎn) 3 往右遍歷秽梅， 節(jié)點(diǎn) 4 往左遍歷，都到了節(jié)點(diǎn) 5剿牺，節(jié)點(diǎn) 5 往下遍歷的話就會(huì)遍歷兩次企垦，所以此時(shí)就會(huì)出現(xiàn)重復(fù)子問(wèn)題

3、采用備忘錄的方式來(lái)存子問(wèn)題的解以避免大量的重復(fù)計(jì)算（剪枝）

既然出現(xiàn)了牢贸，那我們就用備忘錄把中間節(jié)點(diǎn)緩存下來(lái)

于是我們的代碼改為如下所示

private static int[][] triangle = {            {2, 0, 0, 0},            {3, 4, 0, 0},            {6, 5, 7, 0},            {4, 1, 8, 3}    };// 記錄中間狀態(tài)的 mapprivate static HashMap<String, Integer> map = new HashMap();public static int traverse(int i, int j) {    String key = i + "" + j;    if (map.get(key) != null) {        return map.get(key);    }    int totalRow = 4; // 總行數(shù)    if (i >=  totalRow - 1) {        return 0;    }    // 往左下節(jié)點(diǎn)走時(shí)    int leftSum = traverse(i+1, j) + triangle[i+1][j];    // 往右下節(jié)點(diǎn)走時(shí)    int rightSum = traverse(i+1, j+1) + triangle[i+1][j+1];    // 記錄每個(gè)節(jié)點(diǎn)往左和往右遍歷的路徑和的最小值    int result = Math.min(leftSum, rightSum);    map.put(key, result);    return result;}

這么一來(lái)竹观，就達(dá)到了剪枝的目的，避免了重復(fù)子問(wèn)題潜索，時(shí)間復(fù)雜度一下子下降到 O(n), 空間復(fù)雜度呢臭增，由于我們用哈希表存儲(chǔ)了所有的節(jié)點(diǎn)的狀態(tài)，所以空間復(fù)雜度是 O(n)竹习。

4誊抛、改用自底向上的方式來(lái)遞推，即動(dòng)態(tài)規(guī)劃

重點(diǎn)來(lái)了整陌，如何采用自底向上的動(dòng)態(tài)規(guī)劃來(lái)解決問(wèn)題呢? 我們這么來(lái)看拗窃，要求節(jié)點(diǎn) 2 到底部邊的最短路徑，只要先求得節(jié)點(diǎn) 3 和 節(jié)點(diǎn) 4 到底部的最短路徑值泌辫，然后取這兩者之中的最小值再加 2 不就是從 2 到底部的最短路徑了嗎随夸，同理，要求節(jié)點(diǎn) 3 或 節(jié)點(diǎn) 4 到底部的最小值震放，只要求它們的左右節(jié)點(diǎn)到底部的最短路徑再取兩者的最小值再加節(jié)點(diǎn)本身的值（3 或 4）即可宾毒。

我們知道對(duì)于三角形的最后一層節(jié)點(diǎn)，它們到底部的最短路徑就是其本身殿遂，于是問(wèn)題轉(zhuǎn)化為了已知最后一層節(jié)點(diǎn)的最小值怎么求倒數(shù)第二層到最開(kāi)始的節(jié)點(diǎn)到底部的最小值了诈铛。先看倒數(shù)第二層到底部的最短路徑怎么求

image

同理，第二層對(duì)于節(jié)點(diǎn) 3 墨礁，它到最底層的最短路徑轉(zhuǎn)化為了 3 到 7幢竹， 6 節(jié)點(diǎn)的最短路徑的最小值，即 9, 對(duì)于節(jié)點(diǎn) 4恩静，它到最底層的最短路徑轉(zhuǎn)化為了 4 到 6焕毫， 10 的最短路徑兩者的最小值，即 10。

image

接下來(lái)要求 2 到底部的路徑就很簡(jiǎn)單了咬荷，只要求 2 到節(jié)點(diǎn) 9 與 10 的最短路徑即可冠句，顯然為 11。

image

于是最終的 11 即為我們所求的值幸乒，接下來(lái)我們來(lái)看看怎么定義 DP 的狀態(tài)與狀態(tài)轉(zhuǎn)移方程懦底。我們要求每個(gè)節(jié)點(diǎn)到底部的最短路徑，于是 DP 狀態(tài) DP[i,j] 定義為 i,j 的節(jié)點(diǎn)到底部的最小值罕扎，DP狀態(tài)轉(zhuǎn)移方程定義如下：

DP[i,j] = min(DP[i+1, j], D[i+1, j+1]) + triangle[i,j]

這個(gè)狀態(tài)轉(zhuǎn)移方程代表要求節(jié)點(diǎn)到最底部節(jié)點(diǎn)的最短路徑只需要求左右兩個(gè)節(jié)點(diǎn)到最底部的最短路徑兩者的最小值再加此節(jié)點(diǎn)本身聚唐！仔細(xì)想想我們上面的推導(dǎo)過(guò)程是不是都是按這個(gè)狀態(tài)轉(zhuǎn)移方程推導(dǎo)的，實(shí)在不明白建議多看幾遍上面的推導(dǎo)過(guò)程腔召，相信不難明白杆查。

DP 狀態(tài) DP[i,j] 有兩個(gè)變量，需要分別從下而上臀蛛，從左到右循環(huán)求出所有的 i,j, 有了狀態(tài)轉(zhuǎn)移方程求出代碼就比較簡(jiǎn)單了亲桦，如下

private static int[][] triangle = {        {2, 0, 0, 0},        {3, 4, 0, 0},        {6, 5, 7, 0},        {4, 1, 8, 3}};public static int traverse() {    int ROW = 4;    int[] mini = triangle[ROW - 1];    // 從倒數(shù)第二行求起，因?yàn)樽詈笠恍械闹当旧硎枪潭ǖ?   for (int i = ROW - 2; i >= 0; i--) {        for (int j = 0; j < triangle[j].length; j++) {            mini[j] = triangle[i][j] + Math.min(mini[j], mini[j+1]);        }    }    return mini[0];}public static  void main(String[] args)  throws Throwable {    int minPathSum = traverse();    System.out.println("sum = " + minPathSum);}

可能有一些人對(duì) mini 數(shù)組的定義有疑問(wèn)浊仆，這里其實(shí)用了一個(gè)比較取巧的方式客峭，首先我們定義 mini 的初始值為最后一行的節(jié)點(diǎn)，因?yàn)樽詈笠恍械拿總€(gè)節(jié)點(diǎn)的 DP[i,j] 是固定值抡柿，只要從倒數(shù)第二行求起即可舔琅，其次我們知道每個(gè)節(jié)點(diǎn)到底部的最短路徑只與它下一層的 D[I+1,j], D[i+1, j] 有關(guān)，所以只要把每一層節(jié)點(diǎn)的 DP[i,j] 求出來(lái)保存到一個(gè)數(shù)組里即可洲劣，就是為啥我們只需要定義一下 mini 一維數(shù)組的原因

image

如圖示：要求節(jié)點(diǎn) 2 到底部的最短路徑备蚓，它只關(guān)心節(jié)點(diǎn) 9， 10囱稽，之前層數(shù)的節(jié)點(diǎn)無(wú)需再關(guān)心郊尝！因?yàn)?9，10 已經(jīng)是最優(yōu)子結(jié)構(gòu)了战惊，所以只保存每層節(jié)點(diǎn)（即一維數(shù)組）的最值即可虚循！

當(dāng)自下而上遍歷完成了，mini[0] 的值即為 DP[0,0],即為節(jié)點(diǎn) 2 到 底部的最短路徑样傍。mini 的定義可能有點(diǎn)繞，大家可以多思考幾遍铺遂，當(dāng)然衫哥，你也可以定義一個(gè)二維數(shù)組來(lái)保存所有的 DP[i,j]，只不過(guò)多耗些空間罷了襟锐。

這里我們?cè)賮?lái)談?wù)?strong>最優(yōu)子結(jié)構(gòu)撤逢，在以上的推導(dǎo)中我們知道每一層節(jié)點(diǎn)到底部的最短路徑依賴于它下層的左右節(jié)點(diǎn)的最短路徑，求得的下層兩個(gè)節(jié)點(diǎn)的最短路徑對(duì)于依賴于它們的節(jié)點(diǎn)來(lái)說(shuō)就是最優(yōu)子結(jié)構(gòu)，最優(yōu)子結(jié)構(gòu)對(duì)于子問(wèn)題來(lái)說(shuō)屬于全局最優(yōu)解蚊荣，這樣我們不必去求節(jié)點(diǎn)到最底層的所有路徑了初狰，只需要依賴于它的最優(yōu)子結(jié)構(gòu)即可推導(dǎo)出我們所要求的最優(yōu)解，所以最優(yōu)子結(jié)構(gòu)有兩層含義互例，一是它是子問(wèn)題的全局最優(yōu)解奢入，依賴于它的上層問(wèn)題只要根據(jù)已求得的最優(yōu)子結(jié)構(gòu)推導(dǎo)求解即可得全局最優(yōu)解，二是它有緩存的含義媳叨，這樣就避免了多個(gè)依賴于它的問(wèn)題的重復(fù)求解（消除重疊子問(wèn)題）腥光。

總結(jié)：仔細(xì)回想一下我們的解題思路，我們先看了本題是否可用遞歸來(lái)解糊秆，在遞歸的過(guò)程中發(fā)現(xiàn)了有重疊子問(wèn)題武福，于是我們又用備忘錄來(lái)消除遞歸中的重疊子問(wèn)題，既然我們發(fā)現(xiàn)了此問(wèn)題可以用遞歸+備忘錄來(lái)求解痘番，自然而然地想到它可以用自底向上的動(dòng)態(tài)規(guī)劃來(lái)求解捉片。是的，求解動(dòng)態(tài)規(guī)劃就按這個(gè)套路來(lái)即可汞舱，最重要的是要找出它的狀態(tài)轉(zhuǎn)移方程伍纫，這需要在自下而上的推導(dǎo)中仔細(xì)觀察。

進(jìn)階：湊零錢

給定不同面額的硬幣 coins 和一個(gè)總金額 amount兵拢。編寫(xiě)一個(gè)函數(shù)來(lái)計(jì)算可以湊成總金額所需的最少的硬幣個(gè)數(shù)翻斟。如果沒(méi)有任何一種硬幣組合能組成總金額，返回 -1说铃。輸入: coins = [1, 2, 5], amount = 11访惜，輸出: 3 解釋: 11 = 5 + 5 + 1輸入: coins = [2], amount = 3，輸出: -1

來(lái)套用一下我們的動(dòng)態(tài)規(guī)劃解題四步曲

一腻扇、判斷是否可用遞歸來(lái)解

對(duì)于 amount 來(lái)說(shuō)债热，如果我們選擇了 coins 中的任何一枚硬幣，則問(wèn)題的規(guī)模(amount)是不是縮小了,再對(duì)縮小的 amount 也選擇 coins 中的任何一枚硬幣,直到再也不能選擇（amount <= 0, amount = 0 代表有符合條件的解幼苛，小于0代表沒(méi)有符合條件的解）窒篱，從描述中我們可以看出問(wèn)題可以分解成子問(wèn)題，子問(wèn)題與原問(wèn)題具有相同的解決問(wèn)題的思路舶沿，同時(shí)也有臨界條件墙杯，符合遞歸的條件，由此可證可以用遞歸求解括荡，接下來(lái)我們來(lái)看看高镐，如何套用遞歸四步曲來(lái)解題

1、定義這個(gè)函數(shù)畸冲，明確這個(gè)函數(shù)的功能,函數(shù)的功能顯然是給定一個(gè) amount嫉髓，用定義好的 coins 來(lái)湊观腊，于是我們定義函數(shù)如下

private static int f(int amount, int[] coins) {}

2、尋找問(wèn)題與子問(wèn)題的關(guān)系算行，即遞推公式這題的遞推關(guān)系比較難推導(dǎo)梧油，我們一起看下，假設(shè) f(amount, coins) 為零錢 amount 的所需要的最少硬幣數(shù)州邢，當(dāng)選中了coins 中的第一枚硬幣之后（即為 coins[0]）儡陨，則需再對(duì)剩余的 amount - coins[0] 金額求最少硬幣數(shù)，即調(diào)用 f(amount - coins[0], coins) ,由此可知當(dāng)選了第一枚硬幣后的遞推公式如下

f(amount, coins) = f(amount-coins[0]) + 1 (這里的 1 代表選擇了第一枚硬幣)

如果選擇了第二偷霉，第三枚呢迄委，遞推公式如下

f(amount, coins) = f(amount-coins[1]) + 1 (這里的 1 代表選擇了第二枚硬幣)f(amount, coins) = f(amount-coins[2]) + 1 (這里的 1 代表選擇了第三枚硬幣)

我們的目標(biāo)是求得所有以上 f(amount, coins) 解的的最小值，于是可以得到我們的總的遞推公式如下

f(amount, coins) = min{ f(amount - coins[i]) + 1) }, 其中 i 的取值為 0 到 coins 的大小类少，coins[i] 表示選擇了此硬幣, 1 表示選擇了coins[i]  這一枚硬幣

3叙身、將第二步的遞推公式用代碼表示出來(lái)補(bǔ)充到步驟 1 定義的函數(shù)中

得出了遞推公式用代碼實(shí)現(xiàn)就簡(jiǎn)單了，來(lái)簡(jiǎn)單看一下

public class Solution {    private static int exchange(int amount, int[] coins) {        // 說(shuō)明零錢剛好湊完        if (amount == 0) {            return 0;        }        // 說(shuō)明沒(méi)有滿足的條件        if (amount < 0) {            return -1;        }        int result = Integer.MAX_VALUE;        for (int i = 0; i < coins.length; i++) {            int subMin = exchange(amount - coins[i], coins);            if (subMin == -1) continue;            result = Math.min(subMin + 1, result);        }        // 說(shuō)明沒(méi)有符合問(wèn)題的解        if (result == Integer.MAX_VALUE) {            return -1;        }        return result;    }    public static  void main(String[] args)  throws Throwable {        int amount = 11;        int[] coins = {1,2,5};        int result = exchange(amount, coins);        System.out.println("result = " + result);    }}

4硫狞、計(jì)算時(shí)間復(fù)雜度這道題的時(shí)間復(fù)雜度很難看出來(lái)信轿，一般看不出來(lái)的時(shí)候我們可以畫(huà)遞歸樹(shù)來(lái)分析，針對(duì) amount = 11 的遞歸樹(shù) 如下

image

前文我們說(shuō)到斐波那契的遞歸樹(shù)是一顆二叉樹(shù)残吩，時(shí)間復(fù)雜度是指數(shù)級(jí)別财忽，而湊零錢的遞歸樹(shù)是一顆三叉樹(shù) ，顯然時(shí)間復(fù)雜度也是指數(shù)級(jí)別!

二泣侮、分析在遞歸的過(guò)程中是否存在大量的重疊子問(wèn)題（動(dòng)態(tài)規(guī)劃第二步）

由上一節(jié)的遞歸樹(shù)可知即彪，存在重疊子問(wèn)題，上一節(jié)中的 9活尊， 8隶校，都重復(fù)算了,所以存在重疊子問(wèn)題！

三蛹锰、采用備忘錄的方式來(lái)存子問(wèn)題的解以避免大量的重復(fù)計(jì)算（剪枝）

既然我們知道存在重疊子問(wèn)題深胳，那么就可以用備忘錄來(lái)存儲(chǔ)中間結(jié)果達(dá)到剪枝的目的

public class Solution {    // 保存中間結(jié)果    private static HashMap<Integer, Integer> map = new HashMap();    // 帶備忘錄的遞歸求解    private static int exchangeRecursive(int amount, int[] coins) {        if (map.get(amount) != null) {            return map.get(amount);        }        // 說(shuō)明零錢已經(jīng)湊完        if (amount == 0) {            return 0;        }        // 說(shuō)明沒(méi)有滿足的條件        if (amount < 0) {            return -1;        }        int result = Integer.MAX_VALUE;        for (int i = 0; i < coins.length; i++) {            int subMin = exchangeRecursive(amount - coins[i], coins);            if (subMin == -1) continue;            result = Math.min(subMin + 1, result);        }        // 說(shuō)明沒(méi)有符合問(wèn)題的解        if (result == Integer.MAX_VALUE) {            return -1;        }        map.put(amount, result);        return result;    }    public static  void main(String[] args)  throws Throwable {        int amount = 11;        int[] coins = {1,2,5};        int result = exchangeRecursive(amount, coins);        System.out.println("result = " + result);    }}

四、改用自底向上的方式來(lái)遞推铜犬，即動(dòng)態(tài)規(guī)劃

前面我們推導(dǎo)出了如下遞歸公式

f(amount, coins) = min{ f(amount - coins[i]) + 1) }, 其中 i 的取值為 0 到 coins 的大小舞终，coins[i] 表示選擇了此硬幣, 1 表示選擇了coins[i]  這一枚硬幣

從以上的遞推公式中我們可以獲取 DP 的解題思路，我們定義 DP(i) 為湊夠零錢 i 需要的最小值癣猾，狀態(tài)轉(zhuǎn)移方程如下

DP[i] =  min{ DP[ i - coins[j] ] + 1 } = min{ DP[ i - coins[j] ]} + 1,  其中 j 的取值為 0 到 coins 的大小敛劝，i 代表取了 coins[j] 這一枚硬幣。

于是我們只要自底向上根據(jù)以上狀態(tài)轉(zhuǎn)移方程依次求解 DP[1], DP[2],DP[3].,....DP[11]纷宇，最終的 DP[11]夸盟，即為我們所求的解

// 動(dòng)態(tài)規(guī)劃求解private static int exchangeDP(int amount, int[] coins) {    int[] dp = new int[amount + 1];    // 初始化每個(gè)值為 amount+1，這樣當(dāng)最終求得的 dp[amount] 為 amount+1 時(shí)呐粘，說(shuō)明問(wèn)題無(wú)解    for (int i = 0; i < amount + 1; i++) {        dp[i] = amount + 1;    }    // 0 硬幣本來(lái)就沒(méi)有满俗，所以設(shè)置成 0    dp[0] = 0;    for (int i = 0; i < amount + 1; i++) {        for (int j = 0; j < coins.length; j++) {            if (i >= coins[j]) {                dp[i] = Math.min(dp[i- coins[j]], dp[i]) + 1;            }        }    }    if (dp[amount] == amount + 1) {        return -1;    }    return dp[amount];}

畫(huà)外音：以上只是求出了湊成零錢的的最小數(shù)量，但如果想求由哪些面值的硬幣構(gòu)成的作岖，該如何修改呢唆垃？

湊零錢這道題還可以用另外一道經(jīng)典的青蛙跳臺(tái)階的思路來(lái)考慮，從最底部最少跳多少步可以跳到第 11 階痘儡，一次可以跳 1辕万，2，5步 沉删。由此可知最后一步一定是跳 1 或 2 或 5 步渐尿，于是如果用 f(n) 代表跳臺(tái)階 n 的最小跳數(shù)，則問(wèn)題轉(zhuǎn)化為了求 f(n-1)矾瑰，f(n-2) 砖茸，f(n-5)的最小值。

image

如圖示：最后一跳一定是跳 1 或 2 或 5 步殴穴，只要求 f(n-1)凉夯，f(n-2) ，f(n-5)的最小值即可

寫(xiě)出遞推表達(dá)式采幌， 即：

 f(n) = min{ f(n-1)劲够，f(n-2)，f(n-5)} + 1 （1代表最后一跳）

我們的 DP 狀態(tài)轉(zhuǎn)移方程對(duì)比一下休傍，可以發(fā)現(xiàn)兩者其實(shí)是等價(jià)的征绎，只不過(guò)這種跳臺(tái)階的方式可能更容易理解。

總結(jié)

本文通過(guò)幾個(gè)簡(jiǎn)單的例子強(qiáng)化了大家動(dòng)態(tài)規(guī)劃的三要素：最優(yōu)子結(jié)構(gòu)磨取，狀態(tài)轉(zhuǎn)移方程人柿，重疊子問(wèn)題的理解，相信大家對(duì)動(dòng)態(tài)規(guī)劃的理解應(yīng)該深刻了許多寝衫，怎么看出是否可以用動(dòng)態(tài)規(guī)劃來(lái)解呢顷扩，先看題目是否可以用遞歸來(lái)推導(dǎo)，在用遞歸推導(dǎo)的過(guò)程如果發(fā)現(xiàn)有大量地重疊子問(wèn)題慰毅，則有兩種方式可以優(yōu)化隘截，一種是遞歸 + 備忘錄，另一種就是采用動(dòng)態(tài)規(guī)劃了汹胃，動(dòng)態(tài)規(guī)劃一般是自下而上的婶芭， 通過(guò)狀態(tài)轉(zhuǎn)移方程自下而上的得出每個(gè)子問(wèn)題的最優(yōu)解（即最優(yōu)子結(jié)構(gòu)），最優(yōu)子結(jié)構(gòu)其實(shí)也是窮舉了所有的情況得出的最優(yōu)解着饥，得出每個(gè)子問(wèn)題的最優(yōu)解后犀农，也就是每個(gè)最優(yōu)解其實(shí)是這個(gè)子問(wèn)題的全局最優(yōu)解，這樣依賴于它的上層問(wèn)題根據(jù)狀態(tài)轉(zhuǎn)移方程自然而然地得出了全局最優(yōu)解宰掉。動(dòng)態(tài)規(guī)劃自下而上的求解方式還有一個(gè)好處就是避免了重疊子問(wèn)題呵哨，因?yàn)橐蕾囉谧訂?wèn)題的上層問(wèn)題可能有很多赁濒，如果采用自頂而下的方式來(lái)求解，就有可能造成大量的重疊子問(wèn)題孟害，時(shí)間復(fù)雜度會(huì)急劇上升拒炎。

參考：

動(dòng)態(tài)規(guī)劃詳解： https://mp.weixin.qq.com/s/Cw39C9MY9Wr2JlcvBQZMcA