動態(tài)規(guī)劃之武林秘籍

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

第一點，大家在學習動態(tài)規(guī)劃時切忌望文生義，因為其名字與其思想八竿子打不著。你可以自己起一個能讓自己記住其思想的名字更好，比如遞推公式法，狀態(tài)轉移方程法等等。

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

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

廢話不多說，進入正題！

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

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

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

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

這就是要點，務必熟記于心，雖然將來我們會看到各種各樣的例子都是印證。

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

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

最優(yōu)子結構性質

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

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

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

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

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

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

重疊子問題性質

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

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

但還是要說一說，再練！??！

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

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

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

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

再來看看 時的遞歸樹：

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

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

DP table（自底向上）

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

比如我們計算 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)。

也就是說，我們只需要存儲子問題的解，而不需要重復計算子問題的解，對上圖進行簡化：

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

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

實現(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];?
????}?
}?

請不要問我上面的代碼空間復雜度明明可以用 就實現(xiàn)，為什么我要寫成 。因為希望大家理解動態(tài)規(guī)劃法的一個核心思想，保存子問題的解，DP table 會保存所有子問題的解 。你期望的可能是下面這樣，那也 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;?
????}?
}?

備忘錄方法（自頂向下）

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

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

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

以求解 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：遞歸調用可理解為入棧操作，而返回則為出棧操作。

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

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

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

實現(xiàn)上只需要對遞歸實現(xiàn)進行稍加改動即可：

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];
????}
}

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

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

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

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

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

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

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

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

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

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

DP 問題最重要的就是確定所有的狀態(tài)和狀態(tài)與狀態(tài)之間的轉移方程。確定狀態(tài)轉移方程是動態(tài)規(guī)劃最難的部分，但也是最基礎的，必須非常謹慎地選擇狀態(tài)，因為狀態(tài)轉移方程的確定取決于你對問題狀態(tài)定義的選擇。那么，狀態(tài)到底是個什么鬼呢？

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

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

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

第三步：構造狀態(tài)轉移方程

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

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

設 n = 6，使用 {1，3，5} 則共有 8 種方式可以構造出 '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)在考慮用動態(tài)規(guī)劃的方法論來解決。首先確定該問題的狀態(tài)，由于參數(shù) n 可以唯一標識任意一個子問題，我們用參數(shù) n 來確定狀態(tài)。所以，上述問題的狀態(tài)就可以表示為 DP[n]，代表使用 {1，3，5} 作為元素可以形成 n 的總的序列數(shù)。

接下來就是計算 DP[n] 了，此時所謂的直覺就很關鍵了。

因為我們僅能使用 ?{1，3，5} 來形成給定的數(shù)字 n ，我們可以先考慮 n = 1,2,3,4,5,6 的結果，就是求出 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

仔細檢查并確認上述三種情況覆蓋了所有可能形成和為 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]

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

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);
}

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

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

這個可以說是動態(tài)規(guī)劃最簡單的部分，我們僅需要存儲子狀態(tài)的解，以便下次使用子狀態(tà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

被復用的子問題的解既可以使用備忘錄進行存儲，也可以使用 DP Table，那么到底哪種方法更好，兩種方法應該如何抉擇呢？帶著問號畫句號。

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

同學一：為了掌握動態(tài)規(guī)劃的內容，我首先會學習一些動態(tài)規(guī)劃的理論，然后再考慮去用大量的動態(tài)規(guī)劃問題進行練習。

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

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

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

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

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

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

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

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

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

狀態(tài)轉移方程：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] 開始，經狀態(tài)轉移方程到達目標狀態(tài) dp[n] .

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

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

還是按照狀態(tài)轉移描述，我們從狀態(tài) dp[n] 開始，經狀態(tài)轉移向下尋找所需要的子狀態(tài)的值，直到找到所有與狀態(tài) ?dp[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));
}

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

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

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

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

子問題的解：當所有的子問題的解都至少要被解一遍，自底向上的動態(tài)規(guī)劃算法通常比自頂向下的備忘錄方法快常數(shù)量級；當求解的問題的子問題空間中的部分子問題不需要計算，僅需求解部分子問題就可以解決原問題，此時備忘錄方法要優(yōu)于動態(tài)規(guī)劃，因為備忘錄自頂向下僅存儲與原問題求解相關的子問題的解。

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

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

總結

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

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

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

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

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

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

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

推薦閱讀：

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

圖解：什么是哈希？

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