聽到 動(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)值，比如最長(zhǎng)公共子序列、最大子段和、最優(yōu)二叉搜索樹等等。
廢話不多說，進(jìn)入正題！
動(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)，那就多讀幾遍，不過下面早已備好：
這就是要點(diǎn)，務(wù)必熟記于心，雖然將來我們會(huì)看到各種各樣的例子都是印證。
動(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ì)」 。
設(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ì)給大家分享。
但是最長(zhǎng)路徑問題就不具有最優(yōu)子結(jié)構(gòu)性質(zhì)，注意這里的最長(zhǎng)路徑指的是兩個(gè)結(jié)點(diǎn)間的最長(zhǎng)簡(jiǎn)單路徑（即不存在環(huán)的路徑）。盜用算法導(dǎo)論中的一張無權(quán)無向圖就可以說明。
從結(jié)點(diǎn) u 到結(jié)點(diǎn) v 有兩條最長(zhǎng)路徑，分別為 u → s → v 和 u → t → v ，但是與最短路徑問題不同，這些最長(zhǎng)路徑不具有最優(yōu)子結(jié)構(gòu)性質(zhì)。比如，從結(jié)點(diǎn) u 到結(jié)點(diǎn) v 有兩條最長(zhǎng)路徑 u → s → v 并不等于從 u 到 s 的最長(zhǎng)路徑 u → t → v → s 與從 s 到 v 的最長(zhǎng)路徑 s → u → t → v 的加和。（更多最優(yōu)子結(jié)構(gòu)的例子，請(qǐng)持續(xù)關(guān)注景禹，筆芯）。
在用遞歸算法自頂向下解決一個(gè)問題時(shí)，每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復(fù)計(jì)算多次。動(dòng)態(tài)規(guī)劃正是利用了這種子問題的重疊性質(zhì)，對(duì)每個(gè)子問題只解一次，而后將其解保存到一個(gè)表格中，當(dāng)再次需要解此子問題時(shí)，只是簡(jiǎn)單地用常數(shù)時(shí)間查看一下結(jié)果。
光說不練假把式，重疊子問題誰不知道呀？
但還是要說一說，再練！??！
動(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);
}
雖然遞歸的代碼簡(jiǎn)單易懂，但卻極其低效。先不說這種遞歸實(shí)現(xiàn)造成?？臻g的極大浪費(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 就是動(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)行簡(jiǎ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í)，只要簡(jiǎn)單地查看該子問題的答案，而不必重新計(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 < MAX; 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ī)劃（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ī)劃問題四步法：
一般情況下，需要求最優(yōu)解的問題（最短路徑問題，最長(zhǎng)公共子序列，最大字段和等等，出現(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ī)劃解決。
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)移方程是 DP 問題最難的部分，需要足夠敏銳的直覺和觀察力，而這兩者都是要通過大量的練習(xí)來獲得。我們用一個(gè)簡(jiǎn)單的問題來理解這個(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 。
這個(gè)可以說是動(dòng)態(tài)規(guī)劃最簡(jiǎn)單的部分，我們僅需要存儲(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 < MAX; 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];
}
被復(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é)二所說的自頂向下的方式。
顧名思義，自底向上就是從底部（遞歸的出口，動(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 < MAX; 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)和簡(jiǎ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 ，喜歡備忘錄就用備忘錄。
可操作性的動(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 % 。
聯(lián)系客服
