小白一個，在看動態規劃的時候，滿腦子都是遞歸。

題主勿須擔心，思維方式特別習慣某種方式很正常。

DP說白了就是一個解決問題的思路——即一個大一點規模的問題可以被拆解為更小的，更容易解決的問題。

拿最簡單的斐波那契問題舉例子，一個大的問題f(n)可以被拆解為小一點的問題f(n-1)和f(n-2)，……直到然後拆到最小的問題f(1)和f(2)。你可以從f(n)從大往小了算，也可以先從f(1), f(2), f(3)……往大了算。再比如leetcode的有個正則表達式匹配的問題，你可以把問題看做是一個大的字元串的匹配pattern，拆解為字元串的一部分匹配pattern的一部分的問題；也可以反過來先匹配一小部分，再不斷讓可以匹配的範圍變大。

很多人把從大往小算的形式稱作遞歸，反過來從小往大了算稱為DP。但實際上只要滿足大規模問題可以拆解為小規模問題，這個思路本身就是DP的，無非是順序不一樣罷了。

所謂【動態規劃】就是指知道了一組小規模問題的答案後，就可以用一個方案（狀態轉移方程）組裝成大一點規模問題的答案的做法而已。為啥叫「動態」呢，因為狀態轉移會和幾個條件相關，而不是一開始就可以無腦寫死（無腦寫死的一般就是貪婪）。

術語上，從大了往小算被稱為」自頂向下「，而從小往大算被稱為」自底向上「。儘管自頂向下和自底向上等價，但自頂向下算一個很容易發生的問題就是重複計算，比如你為了算f(5)，普通的遞歸方式要重複計算很多很多次f(3), f(2)……。這些計算都是浪費的，實際表現比自底向上差的多（但再強調下，二者的思路沒本質差別，僅僅是計算浪費不浪費的問題）。但你可以加cache，每次遞歸的函數的參數都可以組裝成一個cache的key。這樣每次遞歸時，可以先檢查一下cache是不是有，有了就不用算了，直接返回。這種帶cache的遞歸DP一般被稱為「記憶化搜索「。記憶化搜索與自頂向上的DP計算方式在演算法複雜度上理論上是一樣的。但cache一般會用map，其實際的複雜度要比直接用數組的自頂向上要大，二者的O(1)是不一樣的。此外記憶化搜索還會引入函數調用的開銷，所以一般記憶化搜索比等價的自底向上要慢那麼一丟丟。

此外自底向上的計算方式還可以優化存儲，比如斐波那契計算時，計算f(n)只需要f(n-1), f(n-2)，所以用兩個變數就行，無須把所有的結果都記錄下來。用go寫大概這樣：

func fib(n int) int {
f0, f1 := 0, 1
for n &> 1 {
f1, f0 = f0 + f1, f1
n--
}
return f1
}

但用記憶化搜索的方式，你是沒法在計算得到f(4)後，把f(1)結果佔用內存給方便的清理掉的。

DP最難的不在於自底向上還是自頂向下，而在於怎麼拆問題。某些問題，如果之前沒做過，你是很難想得到「這個問題還能這麼拆」。不信？可以去看看LeetCode有一道「戳氣球」的題目。我自己第一次看時雖然能猜到它是用DP，但打死都想不出來怎麼拆，直到看了題解。因此大家想不出來DP，不是因為不知道DP的代碼框架怎麼做，而是拆解問題的思路實在太古怪，太反常識。這就需要刷題去多多適應。

But，這些反常識的方法也是人想出來的。此時也是去了解那些聰明人的腦洞的好機會：）。你也許會驚訝於人思維方式的差異的巨大。

在現實工程中，有些問題即便是可以DP，但因為拆解方案對於大部分人來說太難想；或者即使想出來，應用面太窄，需求小小的一個變化就會讓整套方案不靈了。因此很多時候，如果複雜度的要求不那麼嚴苛，還是用暴力要好一些。因此DP更常見於面試題里，證明候選人「知道像計算機專業從業者那樣思考」。但這並不是說DP不重要，在計算機科學裡，這個思路非常非常重要，只不過工程上不光要考慮演算法複雜度，還要考慮可維護性問題而已。如果場景恰當，當然還是要用。比方說，我們之前做的「計算基金最大回撤」就用DP，實際上就是LeetCode里「買賣股票最佳時機」解題方案的鏡像——就是一個算回撤，一個算正向收益的區別。

回到DP本身，題主不妨試試這樣做。既然題主的思維方式覺得自頂向下很舒服，那就總是先用遞歸實現自頂向下DP。通過後加上Cache用記憶化搜索的方式寫代碼。再改寫成等價的自頂向上的做法。反覆做幾次看看思路上能不能貫通。但同時，我也遇到過寫自底向上很舒服，反過來就彆扭的人。

當然，雖然二者等價，我依然遇到過很難自底向上寫的問題。此時一般是很難找到一個很簡單的從小到大的規律，這就不如用遞歸+cache。cache的規則就很簡單，算過了就cache，沒算過就沒cache，遞歸調用中參數出現的規律不需要操心。

同時，也有反過來的情況，自底向上很難寫。主要是這類問題的遞歸方式相對好理解，但自底向上時就要讓dp[i][j]表達一些比較模糊，很難說清楚的概念，讓編碼變得很彆扭。所以遇到這種情況就用容易理解的形式寫就好。

最後，遞歸能夠在DP這個思路里支持實現自頂向下，但也不一定就用在DP里。遞歸適合的場景要更加廣泛。比如dfs/bfs這樣的搜索場景就可以用遞歸做。遞歸還可以用來做模擬，比如A對B做一件事、B又要對C和D做一件事，D又要對A和B做一件事……。用遞歸來實現很直觀。

動態規劃（DP 即 Dynamic Programming）指的是題型，即解題思路；而遞歸（Recursion）指的是解題方法，即實現細節。

動態規劃類題型一般有兩種實現方式：

  • bottom-up 即 table-fill（這個我不知道怎麼翻譯）
  • top-down 即遞歸（recursion）

至於具體的不同可以看補充材料[1]。

下面是這兩種方式的詳細舉例。

方法一：bottom-up（table-fill）

function fib(n) {
const arr = [0, 1, 1];
for(let i=3; i&<=n; i++) { arr[i] = arr[i-2] + arr[i-1]; } return arr[n]; }

時間複雜度：O(n)

空間複雜度：O(n)

這種實現方法的好處在於用空間換時間。時間優化了成了 O(n)，但空間也變成了 O(n)。所以一般一維的 DP 大概會用變數來寫。

function fib(n) {
let result = 1;
let first = 1;
let last = 1;
for(let i = 3; i &<= n; i++) { first = last; last = result; result = first + last; } return result; }

時間複雜度：O(n)

空間複雜度：O(1)

這樣一來空間複雜度瞬間降低了一個級別，變為常數級別 O(1)。「利潤」非常可觀。二維及以上的 DP 則會用滾動數組（rolling array）來優化。這裡就不舉例了，大家自行搜索就能看到很多例子。

方法二：top-down（recursion）

function fib(n) {
if(n === 1 || n === 2){
return 1;
}else{
return fib(n-2) + fib(n-1);
}
}

這種實現方法的優勢在於對於每一步看得非常明白，大家能夠輕而易舉地了解什麼是斐波那契數列，對於理解這個結構非常有幫助。但不好的地方在於時間複雜度非常低，低到令人髮指、實際應用中不可接受的地步。

Upper bound time complexity: [公式]

Tight upper bound time complexity: [公式]

具體推算比較枯燥，可以看這裡[2]。

時間複雜度： [公式]

空間複雜度：O(1)

如果你面試的時候僅僅只能寫出這種實現，那基本上這一輩子也與大廠無緣了。

一種常見的優化手段就是上記憶化緩存 （Memoization）。

function fib(n, memo) {
if(n === 1 || n === 2){
return 1;
}else if(n in memo){
return memo[n];
}else{
memo[n] = fib(n-2, memo) + fib(n-1, memo);
}
return memo[n];
}

console.log(fib(8, {}));

時間複雜度：O(n)

空間複雜度：O(n)

這裡由於有了 memo 不用重複運算，基本上只會跑 n 次，所以時間複雜度為 O(n)，空間複雜度為 O(n)。

所以一般的動態規劃問題考察中，大家會直接上最優解即 bottom-up 的 table-fill，並且用變數或者滾動數組來優化空間。但值得注意的是最優解並不意味著是最容易理解的實現方式。一般 recurision + memo（業界也叫 DFS + memo）被稱為是萬金油式的 DP，沒有它解不了的題目。而且時間複雜度和空間複雜度都有很好的平衡。

聰明的讀者，你會選擇哪種實現方式呢？歡迎留言和我討論。

我的專欄還有更多類似的分析和我的學習筆記，如果你喜歡，歡迎進來看看。

編程規劃?

zhuanlan.zhihu.com圖標

參考

  1. ^bottom-up vs top-down https://stackoverflow.com/questions/6164629/what-is-the-difference-between-bottom-up-and-top-down
  2. ^recursive fibonacci https://www.geeksforgeeks.org/time-complexity-recursive-fibonacci-program/

遞歸是動態規劃的一種實現方式(帶備忘的自頂向下方法)，也就是記憶化搜索，除此之外還有遞推(自底向上方法)。而動態規劃是一種具體的思想.

動態規劃適用於子問題重疊的最優化問題 (Optimization Problem)，求解的是一個最優解而不是最優解，因為可能不只有一個解達到最優值。

動態規劃有兩種等價的實現方法，第一種是帶備忘的自頂向下法 (Top-Down With Memoization)，此方法仍按自然的遞歸形式編寫過程，但過程保存每個子問題的解。當需要一個子問題的解時，先檢查是否已經保存過此解，如果是那就直接返回保存的值，從而節省計算時間;否則，按通常方法計算這個子問題，我們稱這個遞歸是帶備忘的 (Memoized)，因為它"記住"了之前已經計算出的結果。而第二種是自底向上法 (Bottom-Up Method)。這種方法一般需要恰當的定義子問題"規模"的概念，使得任意子問題的求解都只依賴於"更小的"子問題的求解，因而我們可以將子問題按照規模排序，按由小至大的順序求解。當求解某個子問題時，它所依賴的那些更小的子問題都已求解完畢，結果已經保存。每個子問題只需要求解一次，當我們求解它時，它的所有前提子問題都已經求解完成。

這兩個術語是不同的概念。動態規劃屬於演算法領域，其思想是拆分問題，利用子問題的解（局部最優解）得到原始問題的解（全局最優解）。遞歸屬於程序設計領域，其含義是程序調用自身。

遞歸的含義是程序調用自身的編程技巧，是一種實現的方式。遞歸與迭代相對。可以列舉常見的簡單問題，例如計算階乘、計算斐波那契數，都可以通過遞歸或迭代的方式實現。理論上，所有的遞歸實現都可以使用迭代實現。實現方式和演算法之間沒有絕對的依賴，同一種演算法可能既能用遞歸實現，也能用迭代實現，例如深度優先搜索，使用遞歸實現是常見的做法，也可以顯性創建一個棧，使用迭代實現。

動態規劃是一種演算法思想，將原始問題拆分成規模更小且與原始問題性質相同的子問題，利用子問題的解得到原始問題的解。動態規劃的適用條件之一是存在重疊子問題。動態規劃的實現方式可以是自頂向下或自底向上。使用自頂向下實現時，通常使用遞歸實現，為了充分利用重疊子問題的性質，需要存儲已經計算得到的子問題的答案，這樣下次在遇到相同子問題的時候就可以直接得到答案而不需要重複計算。使用自底向上實現時，通常使用迭代實現，此時可以確保每個子問題只會被計算一次而不會被重複計算。

大多數情況下，動態規劃都是使用自底向上實現的，而另一種演算法則常用自頂向下實現，那就是分治。分治通常使用遞歸實現，也是將原始問題拆分成規模更小且與原始問題性質相同的子問題，利用子問題的解得到原始問題的解。動態規劃和分治的主要區別是重疊子問題的存在以及實現方式。如果存在重疊子問題，使用動態規劃可以有效降低時間複雜度和空間複雜度。如果不存在重疊子問題，則可以使用分治。

說明動態規劃和分治的區別的一個典型的例子是斐波那契數。斐波那契數的定義是，f(0)=0，f(1)=1，當n&>1時f(n)=f(n-1)+f(n-2)。對於給定的n，需要計算對應的斐波那契數f(n)。斐波那契數的問題如果用分治求解，不加任何緩存，則時間複雜度和空間複雜度會高達O(2^n)，因此分治顯然不是合適的做法。由於存在重複子問題，動態規劃是更合適的做法，時間複雜度和空間複雜度都可以降低到O(n)，如果使用自底向上的做法，還可以使用空間優化，將空間複雜度降低到O(1)。

回到問題，動態規劃是演算法思想，可以有多種實現方式，遞歸是使用自頂向下實現的常用的方式，使用遞歸的方法解動態規劃問題時，為了充分利用重疊子問題的性質，需要存儲已經計算得到的子問題的答案。

一般不是 動態規劃比貪心；遞歸比loop嗎…

推薦閱讀：
相关文章