二、湊零錢問題

先看下題目：給你k種面值的硬幣，面值分別為c1, c2 ... ck，每種硬幣的數(shù)量無限，再給一個總金額amount，問你最少需要幾枚硬幣湊出這個金額，如果不可能湊出，算法返回 -1 。算法的函數(shù)簽名如下：

// coins 中是可選硬幣面值，amount 是目標金額
int coinChange(int[] coins, int amount);

比如說k = 3，面值分別為 1，2，5，總金額amount = 11。那么最少需要 3 枚硬幣湊出，即 11 = 5 + 5 + 1。

你認為計算機應該如何解決這個問題？顯然，就是把所有肯能的湊硬幣方法都窮舉出來，然后找找看最少需要多少枚硬幣。

1、暴力遞歸

首先，這個問題是動態(tài)規(guī)劃問題，因為它具有「最優(yōu)子結構」。 要符合「最優(yōu)子結構」，子問題間必須互相獨立 。啥叫相互獨立？你肯定不想看數(shù)學證明，我用一個直觀的例子來講解。

比如說，你的原問題是考出最高的總成績，那么你的子問題就是要把語文考到最高，數(shù)學考到最高…… 為了每門課考到最高，你要把每門課相應的選擇題分數(shù)拿到最高，填空題分數(shù)拿到最高…… 當然，最終就是你每門課都是滿分，這就是最高的總成績。

得到了正確的結果：最高的總成績就是總分。因為這個過程符合最優(yōu)子結構，“每門科目考到最高”這些子問題是互相獨立，互不干擾的。

但是，如果加一個條件：你的語文成績和數(shù)學成績會互相制約，此消彼長。這樣的話，顯然你能考到的最高總成績就達不到總分了，按剛才那個思路就會得到錯誤的結果。因為子問題并不獨立，語文數(shù)學成績無法同時最優(yōu)，所以最優(yōu)子結構被破壞。

回到湊零錢問題，為什么說它符合最優(yōu)子結構呢？比如你想求amount = 11時的最少硬幣數(shù)（原問題），如果你知道湊出amount = 10的最少硬幣數(shù)（子問題），你只需要把子問題的答案加一（再選一枚面值為 1 的硬幣）就是原問題的答案，因為硬幣的數(shù)量是沒有限制的，子問題之間沒有相互制，是互相獨立的。

那么，既然知道了這是個動態(tài)規(guī)劃問題，就要思考 如何列出正確的狀態(tài)轉(zhuǎn)移方程 。

先確定「狀態(tài)」 ，也就是原問題和子問題中變化的變量。由于硬幣數(shù)量無限，所以唯一的狀態(tài)就是目標金額amount。

然后確定dp函數(shù)的定義 ：函數(shù) dp(n)表示，當前的目標金額是n，至少需要dp(n)個硬幣湊出該金額。

然后確定「選擇」并擇優(yōu) ，也就是對于每個狀態(tài)，可以做出什么選擇改變當前狀態(tài)。具體到這個問題，無論當?shù)哪繕私痤~是多少，選擇就是從面額列表coins中選擇一個硬幣，然后目標金額就會減少：

# 偽碼框架
def coinChange(coins: List[int], amount: int):
    # 定義：要湊出金額 n，至少要 dp(n) 個硬幣
    def dp(n):
        # 做選擇，需要硬幣最少的那個結果就是答案
        for coin in coins:
            res = min(res, 1 + dp(n - coin))
        return res
    # 我們要求目標金額是 amount
    return dp(amount)

最后明確 base case ，顯然目標金額為 0 時，所需硬幣數(shù)量為 0；當目標金額小于 0 時，無解，返回 -1：

def coinChange(coins: List[int], amount: int):

    def dp(n):
        # base case
        if n == 0: return 0
        if n < 0: return -1
        # 求最小值，所以初始化為正無窮
        res = float('INF')
        for coin in coins:
            subproblem = dp(n - coin)
            # 子問題無解，跳過
            if subproblem == -1: continue
            res = min(res, 1 + subproblem)

        return res if res != float('INF') else -1

    return dp(amount)

至此，狀態(tài)轉(zhuǎn)移方程其實已經(jīng)完成了，以上算法已經(jīng)是暴力解法了，以上代碼的數(shù)學形式就是狀態(tài)轉(zhuǎn)移方程：

至此，這個問題其實就解決了，只不過需要消除一下重疊子問題，比如amount = 11, coins = {1,2,5}時畫出遞歸樹看看：

時間復雜度分析：子問題總數(shù) x 解決每個子問題的時間 。

子問題總數(shù)為遞歸樹節(jié)點個數(shù)，這個比較難看出來，是 O(n^k)，總之是指數(shù)級別的。每個子問題中含有一個 for 循環(huán)，復雜度為 O(k)。所以總時間復雜度為 O(k * n^k)，指數(shù)級別。

2、帶備忘錄的遞歸

只需要稍加修改，就可以通過備忘錄消除子問題：

def coinChange(coins: List[int], amount: int):
    # 備忘錄
    memo = dict()
    def dp(n):
        # 查備忘錄，避免重復計算
        if n in memo: return memo[n]

        if n == 0: return 0
        if n < 0: return -1
        res = float('INF')
        for coin in coins:
            subproblem = dp(n - coin)
            if subproblem == -1: continue
            res = min(res, 1 + subproblem)

        # 記入備忘錄
        memo[n] = res if res != float('INF') else -1
        return memo[n]

    return dp(amount)

不畫圖了，很顯然「備忘錄」大大減小了子問題數(shù)目，完全消除了子問題的冗余，所以子問題總數(shù)不會超過金額數(shù) n，即子問題數(shù)目為 O(n)。處理一個子問題的時間不變，仍是 O(k)，所以總的時間復雜度是 O(kn)。

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

當然，我們也可以自底向上使用 dp table 來消除重疊子問題，dp數(shù)組的定義和剛才dp函數(shù)類似，定義也是一樣的：

dp[i] = x表示，當目標金額為i時，至少需要x枚硬幣 。

int coinChange(vector<int>& coins, int amount) {
    // 數(shù)組大小為 amount + 1，初始值也為 amount + 1
    vector<int> dp(amount + 1, amount + 1);
    // base case
    dp[0] = 0;
    for (int i = 0; i < dp.size(); i++) {
        // 內(nèi)層 for 在求所有子問題 + 1 的最小值
        for (int coin : coins) {
            // 子問題無解，跳過
            if (i - coin < 0) continue;
            dp[i] = min(dp[i], 1 + dp[i - coin]);
        }
    }
    return (dp[amount] == amount + 1) ? -1 : dp[amount];
}

PS：為啥dp數(shù)組初始化為amount + 1呢，因為湊成amount金額的硬幣數(shù)最多只可能等于amount（全用 1 元面值的硬幣），所以初始化為amount + 1就相當于初始化為正無窮，便于后續(xù)取最小值。

三、最后總結

第一個斐波那契數(shù)列的問題，解釋了如何通過「備忘錄」或者「dp table」的方法來優(yōu)化遞歸樹，并且明確了這兩種方法本質(zhì)上是一樣的，只是自頂向下和自底向上的不同而已。

第二個湊零錢的問題，展示了如何流程化確定「狀態(tài)轉(zhuǎn)移方程」，只要通過狀態(tài)轉(zhuǎn)移方程寫出暴力遞歸解，剩下的也就是優(yōu)化遞歸樹，消除重疊子問題而已。

如果你不太了解動態(tài)規(guī)劃，還能看到這里，真得給你鼓掌，相信你已經(jīng)掌握了這個算法的設計技巧。

計算機解決問題其實沒有任何奇技淫巧，它唯一的解決辦法就是窮舉 ，窮舉所有可能性。算法設計無非就是先思考“如何窮舉”，然后再追求“如何聰明地窮舉”。

列出動態(tài)轉(zhuǎn)移方程，就是在解決“如何窮舉”的問題。之所以說它難，一是因為很多窮舉需要遞歸實現(xiàn)，二是因為有的問題本身的解空間復雜，不那么容易窮舉完整。

備忘錄、DP table 就是在追求“如何聰明地窮舉”。用空間換時間的思路，是降低時間復雜度的不二法門，除此之外，試問，還能玩出啥花活？