聽到 動(dòng)態(tài)規(guī)劃 這個(gè)響亮的大名你可能已經(jīng)望而卻步，那是因?yàn)檫@個(gè)響亮的名字真的真的很具有迷惑性，不像遞歸、回溯和貪心等等算法一樣，其文即其意，而動(dòng)態(tài)規(guī)劃則不同，很容易望文生義，真可謂害人不淺，今天我就帶大家一起扒一扒 動(dòng)態(tài)規(guī)劃 的褲子。

第一點(diǎn)，大家在學(xué)習(xí)動(dòng)態(tài)規(guī)劃時(shí)切忌望文生義，因?yàn)槠涿峙c其思想八竿子打不著。你可以自己起一個(gè)能讓自己記住其思想的名字更好，比如遞推公式法，狀態(tài)轉(zhuǎn)移方程法等等。

第二點(diǎn)，與其說動(dòng)態(tài)規(guī)劃是一個(gè)算法，還不如說是解決問題的方法論。

第三點(diǎn)，動(dòng)態(tài)規(guī)劃的一般形式就是求最優(yōu)值，比如最長公共子序列、最大子段和、最優(yōu)二叉搜索樹等等。

廢話不多說，進(jìn)入正題！

動(dòng)態(tài)規(guī)劃的基本思想

動(dòng)態(tài)規(guī)劃算法與分治法類似，其基本思想就是將待求解問題分解成若干子問題，先求解子問題，然后從這些子問題的解得到原問題的解。與分治法不同的是，適合動(dòng)態(tài)規(guī)劃法求解的問題，經(jīng)分解得到的子問題往往不是相互獨(dú)立的。若用分治法來解這類問題，則分解得到的子問題數(shù)目太多，以至于最后解決原問題需要耗費(fèi)指數(shù)時(shí)間。然而，不同子問題的數(shù)目常常只有多項(xiàng)式量級(jí)。在用分治法求解時(shí)，有些子問題被重復(fù)結(jié)算了很多次。如果我們能夠保存已經(jīng)解決的子問題的答案，而在需要時(shí)再找出已求得的答案，這樣就可以避免大量的重復(fù)計(jì)算，從而得到多項(xiàng)式時(shí)間復(fù)雜度的算法。為了達(dá)到次目的，可以用一個(gè)表來記錄所有已解決的子問題的答案，不管該子問題以后是否被用到，只要它被計(jì)算過，就將其結(jié)果填入表中。這就是動(dòng)態(tài)規(guī)劃的基本思想。

你看了肯定沒有抓住重點(diǎn)，那就多讀幾遍，不過下面早已備好：

1. 將待求解問題分解成若干子問題，先求解子問題，然后從這些子問題的解得到原問題的解；
2. 經(jīng)分解得到的子問題往往不是相互獨(dú)立的；
3. 保存已經(jīng)解決的子問題的答案，避免重復(fù)計(jì)算。

這就是要點(diǎn)，務(wù)必熟記于心，雖然將來我們會(huì)看到各種各樣的例子都是印證。

動(dòng)態(tài)規(guī)劃的基本要素

動(dòng)態(tài)規(guī)劃算法就是將待求解問題分解成若干子問題，先求解子問題并保存子問題的答案避免重復(fù)計(jì)算，然后從這些子問題的解得到原問題的解。而如何斷定一個(gè)問題是否可以用動(dòng)態(tài)規(guī)劃來解決，就需要掌握動(dòng)態(tài)規(guī)劃的兩個(gè)基本要素，「最優(yōu)子結(jié)構(gòu)性質(zhì)」 和「重疊子問題性質(zhì)」 。

最優(yōu)子結(jié)構(gòu)性質(zhì)

設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法的第一步通常是要刻畫最優(yōu)解的結(jié)構(gòu)。當(dāng)問題的最優(yōu)解包含了其子問題的最優(yōu)解時(shí)，稱該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì) 。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)提供了該問題可用動(dòng)態(tài)規(guī)劃求解的重要線索。

例如，最短路徑問題有如下的最優(yōu)子結(jié)構(gòu)：

結(jié)點(diǎn) x 是從源結(jié)點(diǎn) u 到目標(biāo)結(jié)點(diǎn) v 的最短路徑上的結(jié)點(diǎn)，則源結(jié)點(diǎn) u 到目標(biāo)結(jié)點(diǎn) v 的最短路徑 7 就等于從源結(jié)點(diǎn) u 到結(jié)點(diǎn) x 的最短路徑 5 加上從結(jié)點(diǎn) x 到目標(biāo)結(jié)點(diǎn) v 的最短路徑 2 的和。源結(jié)點(diǎn) u 到目標(biāo)結(jié)點(diǎn) v 的最短路徑就是要求解的最優(yōu)解，源結(jié)點(diǎn) u 到結(jié)點(diǎn) x 的最短路徑和從結(jié)點(diǎn) x 到目標(biāo)結(jié)點(diǎn) v 的最短路徑均為子問題的最優(yōu)解，而問題的最優(yōu)解包含了其子問題的最優(yōu)解，則該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。

弗洛伊德算法（ Floyd–Warshall Algorithm）和貝爾曼-福特算法（Bellman - Ford algorithm）都是解決單源點(diǎn)最短路徑的經(jīng)典動(dòng)態(tài)規(guī)劃算法，以后有機(jī)會(huì)定會(huì)給大家分享。

但是最長路徑問題就不具有最優(yōu)子結(jié)構(gòu)性質(zhì)，注意這里的最長路徑指的是兩個(gè)結(jié)點(diǎn)間的最長簡單路徑（即不存在環(huán)的路徑）。盜用算法導(dǎo)論中的一張無權(quán)無向圖就可以說明。

從結(jié)點(diǎn) u 到結(jié)點(diǎn) v 有兩條最長路徑，分別為 u → s → v 和 u → t → v ，但是與最短路徑問題不同，這些最長路徑不具有最優(yōu)子結(jié)構(gòu)性質(zhì)。比如，從結(jié)點(diǎn) u 到結(jié)點(diǎn) v 有兩條最長路徑 u → s → v 并不等于從 u 到 s 的最長路徑 ?u → t → v → s 與從 s 到 v 的最長路徑 s → u → t → v 的加和。（更多最優(yōu)子結(jié)構(gòu)的例子，請(qǐng)持續(xù)關(guān)注景禹，筆芯）。

重疊子問題性質(zhì)

在用遞歸算法自頂向下解決一個(gè)問題時(shí)，每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復(fù)計(jì)算多次。動(dòng)態(tài)規(guī)劃正是利用了這種子問題的重疊性質(zhì)，對(duì)每個(gè)子問題只解一次，而后將其解保存到一個(gè)表格中，當(dāng)再次需要解此子問題時(shí)，只是簡單地用常數(shù)時(shí)間查看一下結(jié)果。

光說不練假把式，重疊子問題誰不知道呀？

但還是要說一說，再練！?。?/p>

動(dòng)態(tài)規(guī)劃經(jīng)分解得到的子問題往往不是相互獨(dú)立的 。如果經(jīng)分解得到的子問題的解之間相互獨(dú)立，比如二分查找（Binary Search）經(jīng)分解得到的子問題之間相互獨(dú)立，不存在 重疊子問題，所以不適合用 動(dòng)態(tài)規(guī)劃，更適合分治算法。而斐波那契數(shù)列問題則更適用于動(dòng)態(tài)規(guī)劃，雖然嚴(yán)格意義上斐波那契數(shù)列的解決并不是動(dòng)態(tài)規(guī)劃的普適應(yīng)用（動(dòng)態(tài)規(guī)劃的一般形式是求最優(yōu)值！），但是對(duì)于我們理解動(dòng)態(tài)規(guī)劃的 「重疊子問題性質(zhì)」 大有裨益！

關(guān)于斐波那契數(shù)列的遞歸實(shí)現(xiàn)，信手拈來：

int?fib(int?n)
{
????if(n?<=?1){
????????return?n;????????
????}
?return?fib(n-1)?+?fib(n-2);
}

雖然遞歸的代碼簡單易懂，但卻極其低效。先不說這種遞歸實(shí)現(xiàn)造成棧空間的極大浪費(fèi)，就僅僅該算法的時(shí)間復(fù)雜度已屬于指數(shù)級(jí)別 了。

再來看看 時(shí)的遞歸樹：

可以看到，fib(3) 被調(diào)用了兩次，如果我們已經(jīng)保存 fib(3) 的值，我們就可以復(fù)用保存的 fib(3) 的值，而不是重新計(jì)算，fib(2) 也是同樣的道理。

保存重疊子問題的解（也就是 fib(3)）有以下兩種方式：

DP table（自底向上）

DP table 就是動(dòng)態(tài)規(guī)劃算法自底向上建立的一個(gè)表格，用于保存每一個(gè)子問題的解，并返回表中的最后一個(gè)解。比如斐波那契數(shù)，我們先計(jì)算 fib(0)，然后 fib(1)，然后 fib(2)，然后 fib(3)，以此類推，直至計(jì)算出 fib(n)。

比如我們計(jì)算 fib(5)，先由 fib(0) + fib(1) 得到 fib(2)，再由 fib(1) + fib(2) 得到 fib(3)，再由 fib(2) + fib(3) 得到 fib(4)，最后由 fib(3) + fib(4) 得到 fib(5)。

也就是說，我們只需要存儲(chǔ)子問題的解，而不需要重復(fù)計(jì)算子問題的解，對(duì)上圖進(jìn)行簡化：

此圖也就是動(dòng)態(tài)規(guī)劃法求斐波那契數(shù)的過程圖。其實(shí)就實(shí)現(xiàn)而言，其實(shí)質(zhì)上是斐波那契數(shù)的迭代實(shí)現(xiàn)，所以我之前說斐波那契數(shù)嚴(yán)格意義上不是動(dòng)態(tài)規(guī)劃所解決的問題，但是其對(duì)于我們理解「重疊子問題性質(zhì)」還有很有幫助的。

對(duì)斐波那契數(shù)列問題，動(dòng)態(tài)規(guī)劃法（自底而上）保存重疊子問題的解的更一般形式為：

實(shí)現(xiàn)起來更是 so easy !

public?class?Fibonacci?
{?
????int?fib(int?n)?
????{?
????????int?f[]?=?new?int[n+1];?//保存子問題的解
????????f[0]?=?0;?
????????f[1]?=?1;?
????????for?(int?i?=?2;?i?<=?n;?i++)?
????????????f[i]?=?f[i-1]?+?f[i-2];?
????????return?f[n];?
????}?
}?

請(qǐng)不要問我上面的代碼空間復(fù)雜度明明可以用 就實(shí)現(xiàn)，為什么我要寫成 。因?yàn)橄Ｍ蠹依斫鈩?dòng)態(tài)規(guī)劃法的一個(gè)核心思想，保存子問題的解，DP table 會(huì)保存所有子問題的解 。你期望的可能是下面這樣，那也 OK。

public?class?Fibonacci?
{?
????int?fib(int?n)?
????{?
????????int?result?=?0;
????????int?fib0?=?0;?
????????int?fib1?=?1;?
????????for?(int?i?=?2;?i?<=?n;?i++){
????????????result?=?fib0?+?fib1;
????????????fib0?=?fib1;
????????????fib1?=?result;
????????}??
????????return?result;?
????}?
}?

備忘錄方法（自頂向下）

備忘錄方法是動(dòng)態(tài)規(guī)劃算法的變形。與動(dòng)態(tài)規(guī)劃方法一樣，備忘錄方法用表格保存已解決的子問題的答案，在下次需要解此子問題時(shí)，只要簡單地查看該子問題的答案，而不必重新計(jì)算。

與動(dòng)態(tài)規(guī)劃方法不同的是，備忘錄方法的遞歸方式是自頂向下的，而動(dòng)態(tài)規(guī)劃算法則是自底向上遞歸的。因此，備忘錄方法的控制結(jié)構(gòu)與直接遞歸方法的控制結(jié)構(gòu)相同，區(qū)別在于備忘錄方法為每個(gè)解過的子問題建立了備忘錄以備需要時(shí)查看，避免相同子問題的重復(fù)求解。

備忘錄方法為每一個(gè)子問題建立一個(gè)記錄項(xiàng)，初始時(shí)，該記錄項(xiàng)存入一個(gè)特殊的值，表示該子問題尚未被解決（比如下面斐波那契數(shù)的備忘錄版本中將其設(shè)置為 -1）。在求解過程中，對(duì)每個(gè)待求解的子問題，首先查看其相應(yīng)的記錄項(xiàng)。若記錄項(xiàng)中存儲(chǔ)的是初始化時(shí)存入的特殊值，則表示該子問題是第一次遇到，此時(shí)計(jì)算出該子問題的解，并保存在相應(yīng)的記錄項(xiàng)中，以備以后查看。若記錄項(xiàng)中存儲(chǔ)的已不是初始化時(shí)存入的特殊值，則表示該子問題已被計(jì)算過，其相應(yīng)的記錄項(xiàng)存儲(chǔ)的是該子問題的答案。此時(shí)，只要從記錄項(xiàng)中取出該子問題的答案即可，而不必重新計(jì)算。

以求解 fib(5) 為例，為求解 fib(5)，要先求解 fib(4)，要求解 fib(4)，要先求解 fib(3)，要求解 fib(2)，則要先求解 fib(1) 和 fib(0)，fib(1) = 1，fib(0) = 0，則直接返回，依次返回 fib(2) = 1，fib(3) = fib(2) + fib(1) = 2，fib(4) = fib(3) + fib(2) = 3，fib(5) = fib(4) + fib(3) = 5。

PS：遞歸調(diào)用可理解為入棧操作，而返回則為出棧操作。

由 fib(5) 的遞歸樹，可以發(fā)現(xiàn)，備忘錄方法與動(dòng)態(tài)規(guī)劃方法一樣，把一顆存在巨量冗余的遞歸樹進(jìn)行剪枝，改造成了一顆不存在冗余的遞歸圖。重疊子問題的解都被保存了起來，用到時(shí)直接查表即可，而不需要重新計(jì)算，這一點(diǎn)備忘錄與動(dòng)態(tài)規(guī)劃方法一樣。不同的是，備忘錄方法是自頂向下對(duì)問題求解，與直接遞歸方法的控制結(jié)構(gòu)相同，而動(dòng)態(tài)規(guī)劃方法是自底向上對(duì)問題求解，與迭代實(shí)現(xiàn)方式的結(jié)構(gòu)一致。

以 fib(5) 為例，備忘錄方法（自頂向下）最終就是這樣：

對(duì)任意一個(gè)斐波那契數(shù)，更一般的備忘錄方法則為下圖這樣，與動(dòng)態(tài)規(guī)劃法正好相反：

實(shí)現(xiàn)上只需要對(duì)遞歸實(shí)現(xiàn)進(jìn)行稍加改動(dòng)即可：

public?class?Fibonacci
{
????final?int?MAX?=?100;?//?備忘錄的大小
????final?int?NIL?=?-1;?//?特殊值
????
????int?lookup[]?=?new?int[MAX];?//?備忘錄數(shù)組
????
????//初始化備忘錄中的值為特殊值?NIL
????void?initializeTable()
????{
????????for(int?i?=?0;?i?????????{
????????????lookup[i]?=?NIL;
????????}
????}
????//斐波那契數(shù)的備忘錄版本
????int?fib(int?n)
????{
????????if(lookup[n]?==?NIL)
????????{
????????????if(n?<=?1)
????????????{
????????????????lookup[n]?=?n;
????????????}
????????????else{
????????????????lookup[n]?=?fib(n-1)?+?fib(n-2);
????????????}
????????}
????????return?lookup[n];
????}
}

動(dòng)態(tài)規(guī)劃方法（DP table）與備忘錄方法都是存儲(chǔ)子問題解的方法，除了解決問題的邏輯不同之外（一個(gè)自底向上，一個(gè)自頂向下），兩者在時(shí)間效率上較為相近，關(guān)于兩者的更多區(qū)別和相同點(diǎn)，以及如何選擇文末解析。

上面講的都是動(dòng)態(tài)規(guī)劃的一些基本概念，并不具有可操作性，下面帶你真正扒一扒動(dòng)態(tài)規(guī)劃！

如何解決動(dòng)態(tài)規(guī)劃問題？

動(dòng)態(tài)規(guī)劃（Dynamic Programming，DP）是在多項(xiàng)式時(shí)間解決特定類型問題的一套方法論，且遠(yuǎn)遠(yuǎn)快于指數(shù)級(jí)別的蠻力法，而且動(dòng)態(tài)規(guī)劃的正確性是可以嚴(yán)格證明的。只不過這種證明對(duì)于解決動(dòng)態(tài)規(guī)劃問題并不具有決定性因素，所以此文也略去了。

解決動(dòng)態(tài)規(guī)劃問題四步法：

1. 辨別是不是一個(gè)動(dòng)態(tài)規(guī)劃問題；
2. 確定狀態(tài)
3. 建立狀態(tài)之間的關(guān)系；
4. 為狀態(tài)添加備忘錄或者DP Table 。

第一步：如何斷定一個(gè)問題是動(dòng)態(tài)規(guī)劃問題？

一般情況下，需要求最優(yōu)解的問題（最短路徑問題，最長公共子序列，最大字段和等等，出現(xiàn) 最 字你就留意），在一定條件下對(duì)排列進(jìn)行計(jì)數(shù)的計(jì)數(shù)問題（丑數(shù)問題）或某些概率問題都可以考慮用動(dòng)態(tài)規(guī)劃來解決。

所有的動(dòng)態(tài)規(guī)劃問題都滿足重疊子問題性質(zhì)，大多數(shù)經(jīng)典的動(dòng)態(tài)規(guī)劃問題還滿足最優(yōu)子結(jié)構(gòu)性質(zhì)，當(dāng)我們從一個(gè)給定的問題中發(fā)現(xiàn)了這些特性，就可以確定其可以用動(dòng)態(tài)規(guī)劃解決。

第二步：確定狀態(tài)

DP 問題最重要的就是確定所有的狀態(tài)和狀態(tài)與狀態(tài)之間的轉(zhuǎn)移方程。確定狀態(tài)轉(zhuǎn)移方程是動(dòng)態(tài)規(guī)劃最難的部分，但也是最基礎(chǔ)的，必須非常謹(jǐn)慎地選擇狀態(tài)，因?yàn)闋顟B(tài)轉(zhuǎn)移方程的確定取決于你對(duì)問題狀態(tài)定義的選擇。那么，狀態(tài)到底是個(gè)什么鬼呢？

「狀態(tài)」 可以視為一組可以唯一標(biāo)識(shí)給定問題中某個(gè)子問題解的參數(shù)，這組參數(shù)應(yīng)盡可能的小，以減少狀態(tài)空間的大小。比如斐波那契數(shù)中，0 , 1, ..., n 就可以視為參數(shù)，而通過這些參數(shù)定義出的 DP[0]，DP[1]，DP[2]，...，DP[n] 就是狀態(tài)，而狀態(tài)與狀態(tài)之間的轉(zhuǎn)移方程就是 DP(n) = DP(n-1) + DP(n-2) 。

再比如，經(jīng)典的背包問題（Knapsack problem）中，狀態(tài)通過 index 和 weight 兩個(gè)參數(shù)來定義，即 DP[index][weight] 。DP[index][weight] ?則表示當(dāng)前從 0 到 index 的物品裝入背包中可以獲得的最大重量。因此，參數(shù) index 和 weight 可以唯一確定背包問題的一個(gè)子問題的解。

所以，當(dāng)確定給定的問題之后，首當(dāng)其沖的就是確定問題的狀態(tài)。動(dòng)態(tài)規(guī)劃算法就是將待求解問題分解成若干子問題，先求解子問題并保存子問題的答案避免重復(fù)計(jì)算，然后從這些子問題的解得到原問題的解。既然確定了一個(gè)一個(gè)的子問題的狀態(tài)，接下來就是確定前一個(gè)狀態(tài)到當(dāng)前狀態(tài)的轉(zhuǎn)移關(guān)系式，也稱狀態(tài)轉(zhuǎn)移方程。

第三步：構(gòu)造狀態(tài)轉(zhuǎn)移方程

構(gòu)造狀態(tài)轉(zhuǎn)移方程是 DP 問題最難的部分，需要足夠敏銳的直覺和觀察力，而這兩者都是要通過大量的練習(xí)來獲得。我們用一個(gè)簡單的問題來理解這個(gè)步驟。

問題描述：給定 3 個(gè)數(shù) {1，3，5}，請(qǐng)問使用這三個(gè)數(shù)，有多少種方式可以構(gòu)造出一個(gè)給定的數(shù) 'n'.(允許重復(fù)和不同順序)。

設(shè) n = 6，使用 {1，3，5} 則共有 8 種方式可以構(gòu)造出 'n' ：

1+1+1+1+1+1

1+1+1+3

1+1+3+1

1+3+1+1

3+1+1+1

3+3

1+5

5+1

我們現(xiàn)在考慮用動(dòng)態(tài)規(guī)劃的方法論來解決。首先確定該問題的狀態(tài)，由于參數(shù) n 可以唯一標(biāo)識(shí)任意一個(gè)子問題，我們用參數(shù) n 來確定狀態(tài)。所以，上述問題的狀態(tài)就可以表示為 DP[n]，代表使用 {1，3，5} 作為元素可以形成 n 的總的序列數(shù)。

接下來就是計(jì)算 DP[n] 了，此時(shí)所謂的直覺就很關(guān)鍵了。

因?yàn)槲覀儍H能使用 ?{1，3，5} 來形成給定的數(shù)字 n ，我們可以先考慮 n = 1,2,3,4,5,6 的結(jié)果，就是求出 n 等于 1，2，3，4，5，6 的狀態(tài)值。

DP[n = 1] = 1，DP[n = 2] = 1, DP[n = 3] = 2，DP[n = 4] = 3，DP[n = 5] = 5，DP[n = 6] = 8。

現(xiàn)在，我們期望得到 DP[n = 7] 的值，我可以利用子狀態(tài)的三種情況得到 n = 7 ：

一、給狀態(tài) DP[n = 6] 的序列均加 1，如下所示：

(1+1+1+1+1+1) + 1

(1+1+1+3) + 1

(1+1+3+1) + 1

(1+3+1+1) + 1

(3+1+1+1) + 1

(3+3) + 1

(1+5) + 1

(5+1) + 1

二、給狀態(tài) DP[4] 的序列均加 3

(1+1+1+1) + 3

(1+3) + 3

(3 + 1) + 3

三、給狀態(tài) DP[2] 的序列均加 5

(1 + 1) + 5

仔細(xì)檢查并確認(rèn)上述三種情況覆蓋了所有可能形成和為 7 的序列，我們就可以說

DP[7] = DP[6] + DP[4] + DP[2] 或者 DP[7] = DP[7 - 1] + DP[7 - 3] + DP[7-5]

推廣一下：DP[n] = DP[n - 1] + DP[n - 3] + DP[n-5]

此時(shí)我們就可以寫出這樣的代碼了:

int?solve(int?n)
{
????if(n?0){
????????return?0;
????}
????
????if(n?==?1?||?n?==?0){
????????return?1;
????}
????return?solve(n-1)?+?solve(n-3)?+?solve(n-5);
}

但是這個(gè)遞歸解法的時(shí)間復(fù)雜度是指數(shù)級(jí)別的，因?yàn)檫f歸解法重復(fù)計(jì)算了子問題的解。所以，第四步考慮加入備忘錄或者DP Table 。

第四步：為狀態(tài)添加備忘錄或者 DP Table

這個(gè)可以說是動(dòng)態(tài)規(guī)劃最簡單的部分，我們僅需要存儲(chǔ)子狀態(tài)的解，以便下次使用子狀態(tài)時(shí)直接查表從內(nèi)存中獲得。

添加備忘錄的代碼：

public?class??DPSolution{
????final?int?MAX?=?100;?//?備忘錄的大小
????final?int?NIL?=?-1;?//?特殊值

????int?lookup[]?=?new?int[MAX];?//?備忘錄數(shù)組

????//初始化備忘錄中的值為特殊值?NIL
????void?initialize()
????{
????????for(int?i?=?0;?i?????????{
????????????lookup[i]?=?NIL;
????????}
????}
????//備忘錄版本
????int?solve(int?n)
????{

????????if(n?0)
????????{
????????????return?0;
????????}
????????if(n?==??1?||?n?==?0){
????????????return?1;
????????}
????????if(lookup[n]?!=?NIL){
????????????return?lookup[n];
????????}

????????return?lookup[n]?=?solve(n-1)?+?solve(n-3)?+?solve(n-5);
????}
????public?static?void?main(String?args[]){
????????DPSolution?dp?=?new?DPSolution();
????????dp.initialize();
????????System.out.println(dp.solve(20));
????}
}

添加 DP Table 的代碼：

final?int?MAX?=?100;?//?備忘錄的大小
int?solve(int?n){
????int?DP[]?=?new?int[MAX];
????DP[1]?=?1;
????DP[2]?=?1;
????DP[3]?=?2;
????DP[4]?=?3;
????DP[5]?=?5;
????for(int?i?=?6;?i?<=?n;?i++){
????????DP[i]?=?DP[i?-?1]?+?DP[i?-?3]?+?DP[i?-?5];
????}
????return?DP[n];
}?

備忘錄 vs DP Table

被復(fù)用的子問題的解既可以使用備忘錄進(jìn)行存儲(chǔ)，也可以使用 DP Table，那么到底哪種方法更好，兩種方法應(yīng)該如何抉擇呢？帶著問號(hào)畫句號(hào)。

雖然在最開始介紹備忘錄方法時(shí)已有涉及，但這里的講解會(huì)更通俗。我們一起來看兩個(gè)同學(xué)學(xué)習(xí)動(dòng)態(tài)規(guī)劃的方式。

同學(xué)一：為了掌握動(dòng)態(tài)規(guī)劃的內(nèi)容，我首先會(huì)學(xué)習(xí)一些動(dòng)態(tài)規(guī)劃的理論，然后再考慮去用大量的動(dòng)態(tài)規(guī)劃問題進(jìn)行練習(xí)。

同學(xué)二：為了掌握動(dòng)態(tài)規(guī)劃的內(nèi)容，我必須練習(xí)一些經(jīng)典的動(dòng)態(tài)規(guī)劃問題，為此我不得不學(xué)習(xí)一些動(dòng)態(tài)規(guī)劃的理論。

兩位同學(xué)說的是同一件事情，區(qū)別在于兩者傳遞信息的方式不同，同學(xué)一可以視為一種自底向上的方式，而同學(xué)二是一種自頂向下的方式。

DP Table 就是同學(xué)一所說的自底向上的方式，備忘錄則是同學(xué)二所說的自頂向下的方式。

DP Table 法（自底向上的動(dòng)態(tài)規(guī)劃）

顧名思義，自底向上就是從底部（遞歸的出口，動(dòng)態(tài)規(guī)劃中稱為 base case）開始，不斷向上回溯，計(jì)算出問題的解。下面看一下 DP Table 的狀態(tài)轉(zhuǎn)移過程。

設(shè) DP 問題的基態(tài)（Base State）為 dp[0] ，目標(biāo)狀態(tài)為 dp[n] 。

如果我們從基態(tài) dp[0] 開始轉(zhuǎn)移，在遵循狀態(tài)轉(zhuǎn)移方程的情況下到達(dá)目標(biāo)狀態(tài) dp[n] ，則將其稱為 “自底向上” 的方法。（dp[0] → dp[n]）

我們可以使用自底向上的方法計(jì)算一個(gè)數(shù)的階乘。

定義狀態(tài)：dp[x] 表示一個(gè)狀態(tài)，即 x 的階乘。

狀態(tài)轉(zhuǎn)移方程：dp[x] = dp[x - 1] * x .

int?dp[]?=?new?int[MAX];
int?dp[0]?=?1;?//?base?state
for(int?i?=?1;?i?<=?n;?i++)
{
????dp[i]?=?dp[i-1]?*?i;
}

上面的從基態(tài) dp[0] 開始，經(jīng)狀態(tài)轉(zhuǎn)移方程到達(dá)目標(biāo)狀態(tài) dp[n] .

PS：注意這里的DP Table 是按照順序填充的，并且我們直接從表中訪問計(jì)算的子狀態(tài)的解。

備忘錄法（自頂向下的方法）

還是按照狀態(tài)轉(zhuǎn)移描述，我們從狀態(tài) dp[n] 開始，經(jīng)狀態(tài)轉(zhuǎn)移向下尋找所需要的子狀態(tài)的值，直到找到所有與狀態(tài) ?dp[n] 相關(guān)的子狀態(tài)，并返回 ?dp[n] ，這就是自頂向下的備忘錄方法。

我們用備忘錄方法解決階乘問題。

int?dp[]?=?new?int[MAX];
for(int?i?=?0;?i??dp[i]?=?-1;
}

int?solve(int?x){
????if(x?==?0){
????????return?1;
????}
????if(dp[x]?!=?-1){
????????return?dp[x];
????}
????return?(dp[x]?=?x?*?solve(x-1));
}

對(duì)于階乘問題，內(nèi)存布局是線性的，所以 dp[] 表是按照線性進(jìn)行填充的。但是當(dāng)考慮二維數(shù)組的情況下，就像最小成本路徑問題一樣，此時(shí)的內(nèi)存將不是按照順序存儲(chǔ)。

狀態(tài)：DP Table 狀態(tài)轉(zhuǎn)移關(guān)系較難確定，備忘錄狀態(tài)轉(zhuǎn)移關(guān)系較易確定。你可以理解為自頂向下推導(dǎo)較為容易，自底向上推導(dǎo)較難。比如 DP[n] = DP[n - 1] + DP[n - 3] + DP[n-5] 的確定。

代碼：當(dāng)約束條件較多的情況下，DP Table 較為復(fù)雜；備忘錄代碼相對(duì)容易實(shí)現(xiàn)和簡單，僅需對(duì)遞歸代碼進(jìn)行改造。

效率：動(dòng)態(tài)規(guī)劃（DP Table）較快，我們可以直接從表中獲取子狀態(tài)的解；備忘錄由于大量的遞歸調(diào)用和返回狀態(tài)操作，速度較慢。

子問題的解：當(dāng)所有的子問題的解都至少要被解一遍，自底向上的動(dòng)態(tài)規(guī)劃算法通常比自頂向下的備忘錄方法快常數(shù)量級(jí)；當(dāng)求解的問題的子問題空間中的部分子問題不需要計(jì)算，僅需求解部分子問題就可以解決原問題，此時(shí)備忘錄方法要優(yōu)于動(dòng)態(tài)規(guī)劃，因?yàn)閭渫涀皂斚蛳聝H存儲(chǔ)與原問題求解相關(guān)的子問題的解。

表空間：DP Table 依次填充所有子狀態(tài)的解；而備忘錄不必填充所有子問題的解，而是按需填充。

至于兩個(gè)該如何選擇，我想你的心中也有數(shù)了，建議按照解動(dòng)態(tài)規(guī)劃的四步驟依次求解，至于第四步，你個(gè)人喜歡用 DP Table 就用 DP Table ，喜歡備忘錄就用備忘錄。

總結(jié)

可操作性的動(dòng)態(tài)規(guī)劃解題步驟：

第一步：斷定一個(gè)問題是不是動(dòng)態(tài)規(guī)劃問題？（重疊子問題、最優(yōu)子結(jié)構(gòu)，“最” 字要注意）。

第二步：確定狀態(tài)及其含義；

第三步：構(gòu)造狀態(tài)轉(zhuǎn)移方程（根據(jù)題目給定的條件，枚舉若干子狀態(tài)，然后嘗試用這些子狀態(tài)構(gòu)造出未知狀態(tài)的解，就可以輕松得到狀態(tài)轉(zhuǎn)移方程，當(dāng)然這一步離不開大量的練習(xí)）。

第四步：為狀態(tài)添加備忘錄或者 DP Table（根據(jù)個(gè)人喜歡，兩者沒有絕對(duì)的好壞之分）。

熟練掌握這四步套路，看它動(dòng)態(tài)規(guī)劃能玩出什么花樣？

PS：我花樣百出，你只能覆蓋我的 80 % 。

推薦閱讀：

漫畫：什么是樹狀數(shù)組？

圖解：什么是哈希？

作者：景禹，一個(gè)追求極致的共享主義者，想帶你一起擁有更美好的生活，化作你的一把傘。