算法技巧就那幾個(gè)套路，如果你心里有數(shù)，就會(huì)輕松很多，本文就來(lái)扒一扒動(dòng)態(tài)規(guī)劃的褲子，形成一套解決這類問(wèn)題的思維框架。廢話不多說(shuō)了，上干貨。

動(dòng)態(tài)規(guī)劃問(wèn)題的一般形式就是求最值 。動(dòng)態(tài)規(guī)劃其實(shí)是運(yùn)籌學(xué)的一種最優(yōu)化方法，只不過(guò)在計(jì)算機(jī)問(wèn)題上應(yīng)用比較多，比如說(shuō)讓你求最長(zhǎng)遞增子序列呀，最小編輯距離呀等等。

既然是要求最值，核心問(wèn)題是什么呢？ 求解動(dòng)態(tài)規(guī)劃的核心問(wèn)題是窮舉 。因?yàn)橐笞钪?，肯定要把所有可行的答案窮舉出來(lái)，然后在其中找最值唄。

動(dòng)態(tài)規(guī)劃就這么簡(jiǎn)單，就是窮舉就完事了？我看到的動(dòng)態(tài)規(guī)劃問(wèn)題都很難?。?/p>

首先，動(dòng)態(tài)規(guī)劃的窮舉有點(diǎn)特別，因?yàn)檫@類問(wèn)題 存在「重疊子問(wèn)題」 ，如果暴力窮舉的話效率會(huì)極其低下，所以需要「?jìng)渫洝够蛘摺窪P table」來(lái)優(yōu)化窮舉過(guò)程，避免不必要的計(jì)算。

而且，動(dòng)態(tài)規(guī)劃問(wèn)題一定會(huì) 具備「最優(yōu)子結(jié)構(gòu)」 ，才能通過(guò)子問(wèn)題的最值得到原問(wèn)題的最值。

另外，雖然動(dòng)態(tài)規(guī)劃的核心思想就是窮舉求最值，但是問(wèn)題可以千變?nèi)f化，窮舉所有可行解其實(shí)并不是一件容易的事，只有列出 正確的「狀態(tài)轉(zhuǎn)移方程 」 才能正確地窮舉。

以上提到的重疊子問(wèn)題、最優(yōu)子結(jié)構(gòu)、狀態(tài)轉(zhuǎn)移方程就是動(dòng)態(tài)規(guī)劃三要素。具體什么意思等會(huì)會(huì)舉例詳解，但是在實(shí)際的算法問(wèn)題中， 寫出狀態(tài)轉(zhuǎn)移方程是最困難的 ，這也就是為什么很多朋友覺(jué)得動(dòng)態(tài)規(guī)劃問(wèn)題困難的原因，我來(lái)提供我研究出來(lái)的一個(gè)思維框架，輔助你思考狀態(tài)轉(zhuǎn)移方程：

明確「狀態(tài)」 -> 定義 dp 數(shù)組/函數(shù)的含義 -> 明確「選擇」-> 明確 base case。

下面通過(guò)斐波那契數(shù)列問(wèn)題和湊零錢問(wèn)題來(lái)詳解動(dòng)態(tài)規(guī)劃的基本原理。前者主要是讓你明白什么是重疊子問(wèn)題（斐波那契數(shù)列嚴(yán)格來(lái)說(shuō)不是動(dòng)態(tài)規(guī)劃問(wèn)題），后者主要集中于如何列出狀態(tài)轉(zhuǎn)移方程。

請(qǐng)讀者不要嫌棄這個(gè)例子簡(jiǎn)單， 只有簡(jiǎn)單的例子才能讓你把精力充分集中在算法背后的通用思想和技巧上，而不會(huì)被那些隱晦的細(xì)節(jié)問(wèn)題搞的莫名其妙 。想要困難的例子，歷史文章里有的是。

一、斐波那契數(shù)列

1、暴力遞歸

斐波那契數(shù)列的數(shù)學(xué)形式就是遞歸的，寫成代碼就是這樣：

int fib(int N) {
    if (N == 1 || N == 2) return 1;
    return fib(N - 1) + fib(N - 2);
}

這個(gè)不用多說(shuō)了，學(xué)校老師講遞歸的時(shí)候似乎都是拿這個(gè)舉例。我們也知道這樣寫代碼雖然簡(jiǎn)潔易懂，但是十分低效，低效在哪里？假設(shè) n = 20，請(qǐng)畫出遞歸樹(shù)。

PS：但凡遇到需要遞歸的問(wèn)題，最好都畫出遞歸樹(shù)，這對(duì)你分析算法的復(fù)雜度，尋找算法低效的原因都有巨大幫助。

這個(gè)遞歸樹(shù)怎么理解？就是說(shuō)想要計(jì)算原問(wèn)題f(20)，我就得先計(jì)算出子問(wèn)題f(19)和f(18)，然后要計(jì)算f(19)，我就要先算出子問(wèn)題f(18)和f(17)，以此類推。最后遇到f(1)或者f(2)的時(shí)候，結(jié)果已知，就能直接返回結(jié)果，遞歸樹(shù)不再向下生長(zhǎng)了。

遞歸算法的時(shí)間復(fù)雜度怎么計(jì)算？子問(wèn)題個(gè)數(shù)乘以解決一個(gè)子問(wèn)題需要的時(shí)間。

子問(wèn)題個(gè)數(shù)，即遞歸樹(shù)中節(jié)點(diǎn)的總數(shù)。顯然二叉樹(shù)節(jié)點(diǎn)總數(shù)為指數(shù)級(jí)別，所以子問(wèn)題個(gè)數(shù)為 O(2^n)。

解決一個(gè)子問(wèn)題的時(shí)間，在本算法中，沒(méi)有循環(huán)，只有 f(n - 1) + f(n - 2) 一個(gè)加法操作，時(shí)間為 O(1)。

所以，這個(gè)算法的時(shí)間復(fù)雜度為 O(2^n)，指數(shù)級(jí)別，爆炸。

觀察遞歸樹(shù)，很明顯發(fā)現(xiàn)了算法低效的原因：存在大量重復(fù)計(jì)算，比如f(18)被計(jì)算了兩次，而且你可以看到，以f(18)為根的這個(gè)遞歸樹(shù)體量巨大，多算一遍，會(huì)耗費(fèi)巨大的時(shí)間。更何況，還不止f(18)這一個(gè)節(jié)點(diǎn)被重復(fù)計(jì)算，所以這個(gè)算法及其低效。

這就是動(dòng)態(tài)規(guī)劃問(wèn)題的第一個(gè)性質(zhì)： 重疊子問(wèn)題 。下面，我們想辦法解決這個(gè)問(wèn)題。

2、帶備忘錄的遞歸解法

明確了問(wèn)題，其實(shí)就已經(jīng)把問(wèn)題解決了一半。即然耗時(shí)的原因是重復(fù)計(jì)算，那么我們可以造一個(gè)「?jìng)渫洝梗看嗡愠瞿硞€(gè)子問(wèn)題的答案后別急著返回，先記到「?jìng)渫洝估镌俜祷?；每次遇到一個(gè)子問(wèn)題先去「?jìng)渫洝估锊橐徊椋绻l(fā)現(xiàn)之前已經(jīng)解決過(guò)這個(gè)問(wèn)題了，直接把答案拿出來(lái)用，不要再耗時(shí)去計(jì)算了。

一般使用一個(gè)數(shù)組充當(dāng)這個(gè)「?jìng)渫洝?，?dāng)然你也可以使用哈希表（字典），思想都是一樣的。

int fib(int N) {
    if (N < 1) return 0;
    // 備忘錄全初始化為 0
    vector<int> memo(N + 1, 0);
    // 初始化最簡(jiǎn)情況
    return helper(memo, N);
}

int helper(vector<int>& memo, int n) {
    // base case 
    if (n == 1 || n == 2) return 1;
    // 已經(jīng)計(jì)算過(guò)
    if (memo[n] != 0) return memo[n];
    memo[n] = helper(memo, n - 1) + 
                helper(memo, n - 2);
    return memo[n];
}

現(xiàn)在，畫出遞歸樹(shù)，你就知道「?jìng)渫洝沟降鬃隽耸裁矗?/p>

實(shí)際上，帶「?jìng)渫洝沟倪f歸算法，把一棵存在巨量冗余的遞歸樹(shù)通過(guò)「剪枝」，改造成了一幅不存在冗余的遞歸圖，極大減少了子問(wèn)題（即遞歸圖中節(jié)點(diǎn)）的個(gè)數(shù)。

遞歸算法的時(shí)間復(fù)雜度怎么算？ 子問(wèn)題個(gè)數(shù)乘以解決一個(gè)子問(wèn)題需要的時(shí)間。

子問(wèn)題個(gè)數(shù)，即圖中節(jié)點(diǎn)的總數(shù)，由于本算法不存在冗余計(jì)算，子問(wèn)題就是f(1),f(2),f(3)…f(20)，數(shù)量和輸入規(guī)模 n = 20 成正比，所以子問(wèn)題個(gè)數(shù)為 O(n)。

解決一個(gè)子問(wèn)題的時(shí)間，同上，沒(méi)有什么循環(huán)，時(shí)間為 O(1)。

所以，本算法的時(shí)間復(fù)雜度是 O(n)。比起暴力算法，是降維打擊。

至此，帶備忘錄的遞歸解法的效率已經(jīng)和迭代的動(dòng)態(tài)規(guī)劃一樣了。實(shí)際上，這種解法和迭代的動(dòng)態(tài)規(guī)劃思想已經(jīng)差不多，只不過(guò)這種方法叫做「自頂向下」，動(dòng)態(tài)規(guī)劃叫做「自底向上」。

啥叫「自頂向下」？ 注意我們剛才畫的遞歸樹(shù)（或者說(shuō)圖），是從上向下延伸，都是從一個(gè)規(guī)模較大的原問(wèn)題比如說(shuō)f(20)，向下逐漸分解規(guī)模，直到f(1)和f(2)觸底，然后逐層返回答案，這就叫「自頂向下」。

啥叫「自底向上」？ 反過(guò)來(lái)，我們直接從最底下，最簡(jiǎn)單，問(wèn)題規(guī)模最小的f(1)和f(2)開(kāi)始往上推，直到推到我們想要的答案f(20)，這就是動(dòng)態(tài)規(guī)劃的思路，這也是為什么動(dòng)態(tài)規(guī)劃一般都脫離了遞歸，而是由循環(huán)迭代完成計(jì)算。

3、dp 數(shù)組的迭代解法

有了上一步「?jìng)渫洝沟膯l(fā)，我們可以把這個(gè)「?jìng)渫洝躬?dú)立出來(lái)成為一張表，就叫做 DP table 吧，在這張表上完成「自底向上」的推算豈不美哉！

int fib(int N) {
    vector<int> dp(N + 1, 0);
    // base case
    dp[1] = dp[2] = 1;
    for (int i = 3; i <= N; i++)
        dp[i] = dp[i - 1] + dp[i - 2];
    return dp[N];
}

畫個(gè)圖就很好理解了，而且你發(fā)現(xiàn)這個(gè) DP table 特別像之前那個(gè)「剪枝」后的結(jié)果，只是反過(guò)來(lái)算而已。實(shí)際上，帶備忘錄的遞歸解法中的「?jìng)渫洝?，最終完成后就是這個(gè) DP table，所以說(shuō)這兩種解法其實(shí)是差不多的，大部分情況下，效率也基本相同。

這里，引出「狀態(tài)轉(zhuǎn)移方程」這個(gè)名詞，實(shí)際上就是描述問(wèn)題結(jié)構(gòu)的數(shù)學(xué)形式：

為啥叫「狀態(tài)轉(zhuǎn)移方程」？為了聽(tīng)起來(lái)高端。你把 f(n) 想做一個(gè)狀態(tài) n，這個(gè)狀態(tài) n 是由狀態(tài) n - 1 和狀態(tài) n - 2 相加轉(zhuǎn)移而來(lái)，這就叫狀態(tài)轉(zhuǎn)移，僅此而已。

你會(huì)發(fā)現(xiàn)，上面的幾種解法中的所有操作，例如 return f(n - 1) + f(n - 2)，dp[i] = dp[i - 1] + dp[i - 2]，以及對(duì)備忘錄或 DP table 的初始化操作，都是圍繞這個(gè)方程式的不同表現(xiàn)形式?？梢?jiàn)列出「狀態(tài)轉(zhuǎn)移方程」的重要性，它是解決問(wèn)題的核心。很容易發(fā)現(xiàn)，其實(shí)狀態(tài)轉(zhuǎn)移方程直接代表著暴力解法。

千萬(wàn)不要看不起暴力解，動(dòng)態(tài)規(guī)劃問(wèn)題最困難的就是寫出狀態(tài)轉(zhuǎn)移方程 ，即這個(gè)暴力解。優(yōu)化方法無(wú)非是用備忘錄或者 DP table，再無(wú)奧妙可言。

這個(gè)例子的最后，講一個(gè)細(xì)節(jié)優(yōu)化。細(xì)心的讀者會(huì)發(fā)現(xiàn)，根據(jù)斐波那契數(shù)列的狀態(tài)轉(zhuǎn)移方程，當(dāng)前狀態(tài)只和之前的兩個(gè)狀態(tài)有關(guān)，其實(shí)并不需要那么長(zhǎng)的一個(gè) DP table 來(lái)存儲(chǔ)所有的狀態(tài)，只要想辦法存儲(chǔ)之前的兩個(gè)狀態(tài)就行了。所以，可以進(jìn)一步優(yōu)化，把空間復(fù)雜度降為 O(1)：

int fib(int n) {
    if (n == 2 || n == 1) 
        return 1;
    int prev = 1, curr = 1;
    for (int i = 3; i <= n; i++) {
        int sum = prev + curr;
        prev = curr;
        curr = sum;
    }
    return curr;
}

有人會(huì)問(wèn)，動(dòng)態(tài)規(guī)劃的另一個(gè)重要特性「最優(yōu)子結(jié)構(gòu)」，怎么沒(méi)有涉及？下面會(huì)涉及。斐波那契數(shù)列的例子嚴(yán)格來(lái)說(shuō)不算動(dòng)態(tài)規(guī)劃，因?yàn)闆](méi)有涉及求最值，以上旨在演示算法設(shè)計(jì)螺旋上升的過(guò)程。

下面，看第二個(gè)例子，湊零錢問(wèn)題。