一文搞懂動態規劃

動態規劃(Dynamic programming，簡稱DP)是一種通過把原問題分解為相對簡單的子問題的方式求解複雜問題的方法。

從面試的角度看，動態規劃是正規算法面試中無論如何都逃不掉的必考題,曾經有一個偉人說過這樣一句話:

那麼為什麼動態規劃會在面試中這麼重要?

其實最主要的原因就是動態規劃非常適合面試，因為動態規劃沒辦法「背」。

我們很多求職者其實是通過背題來面試的，而之前這個做法屢試不爽，什麼翻轉二叉樹、翻轉鍊表，快排、歸併、冒泡一頓背，基本上也能在面試中渾水摸魚過去，其實這哪是考算法能力、算法思維，這就是考誰的備戰態度好，願意花時間去背題而已，把連背都懶得背的篩出去就完事了。

但是隨著網際網路遇冷，人才供給進一步過熱，背題的人越來越多，面試的門檻被增加了，因此這個時候需要一種非常考驗算法思維、變化多端而且容易設計的題目類型，動態規劃就完美符合這個要求。

比如 LeetCode 中有1261道算法類題目,其中動態規劃題目占據了近200道，動態規劃能占據總題目的 1/6 的比例,可見其火熱程度。

更重要的是，動態規劃的題目難度以中高難度為主:

所以,既然我們已經知道這是算法面試的必考題了,我們怎麼準備都不為過,本文盡筆者最大努力把動態規劃講清楚。

從「錢」講起

我們在前面內容了解到了貪心算法可以解決「硬幣找零問題」，但是那只是在部分情況下可以解決而已，因為題目中給出的錢幣面值為 1、5、25，我們現實生活中我們現行的第五套人民幣面值分別為100、50、20、10、5、1,我們的人民幣是可以用貪心算法找零的。

那麼有什麼情況下不能用貪心算法嗎？比如一個算法星球的央行發行了奇葩幣，幣值分別為1、5、11，要湊夠15元，這個時候貪心算法就失效了。

我們可以算一下，按照貪心算法的策略，我們先拿出最大面值的11，剩下的4個分別對應四個1元的奇葩幣，這總共需要五個奇葩幣才能湊夠15元。

而實際上我們簡單一算，就知道最少情況是拿出3個五元的奇葩幣才能湊夠15元。

這裡就有問題了,貪心算法的弊端在這種特殊面值錢幣面前展露無疑,原因就在於「只顧眼前，無大局觀」，在先拿出最大的 11 面值的奇葩幣後就徹底把周旋餘地堵死了,因為剩下的 4 要想湊足付出的代價是非常高的,我們需要依次拿出4個面值為1的奇葩幣。

改進計算策略

那麼既然貪心算法已經不適用於這種場景了,我們應該如何改變計算策略呢?

當我們面試過程中遇到這種問題時,如果一時沒有思路,也要想到一種萬能算法--暴力破解。

我們分析一下上述題目,它的問題其實是「給定一組面額的硬幣,我們用現有的幣值湊出n最少需要多少個幣」。

我們要湊夠這個 n,只要 n 不為0,那麼總會有處在最後一個的硬幣,這個硬幣恰好湊成了 n,比如我們用 {11,1,1,1,1} 來湊15,前面我們拿出 {11,1,1,1} ,最後我們拿出 {1} 正好湊成 15。

如果用 {5,5,5} 來湊15,最後一個硬幣就是5,我們按照這個思路捋一捋,：

• 那麼假設最後一個硬幣為11的話，那麼剩下4，這個時候問題又變成了，我們湊出 n-11 最少需要多少個幣,此時n=4，我們只能取出4個面值為1的幣
• 如果假設最後一個硬幣為 5 的話，這個時候問題又變成了，我們用現有的幣值湊出 n-5 最少需要多少個幣

大家發現了沒有，我們的問題提可以不斷被分解為「我們用現有的幣值湊出 n 最少需要多少個幣」,比如我們用 f(n) 函數代表 「湊出 n 最少需要多少個幣」.

把「原有的大問題逐漸分解成類似的但是規模更小的子問題」這就是最優子結構,我們可以通過自底向上的方式遞歸地從子問題的最優解逐步構造出整個問題的最優解。

這個時候我們分別假設 1、5、11 三種面值的幣分別為最後一個硬幣的情況：

• 最後一枚硬幣的面額為 11: min = f(4) + 1
• 最後一枚硬幣的面額為 5: min = f(10) + 1
• 最後一枚硬幣的面額為 1: min = f(14) + 1

這個時候大家發現問題所在了嗎?最少找零 min 與 f(4)、f(10)、f(14) 三個函數解中的最小值是有關的，畢竟後面的「+1」是大家都有的。

假設湊的硬幣總額為 n，那麼 f(4) = f(n-11) 、 f(10) = f(n-5) 、 f(14) = f(n-1) ，我們得出以下公式:

f(n) = min{f(n-1), f(n-5), f(n-11)} + 1

我們再具體到上面公式中 f(n-1) 湊夠它的最小硬幣數量是多少,是不是又變成下面這個公式:

f(n-1) = min{f(n-1-1), f(n-1-5), f(n-1-11)} + 1

以此類推...

這真是似曾相識,這不就是遞歸嗎?

是的,我們可以通過遞歸來求出最少找零問題的解,代碼如下:

function f(n) {
    if(n === 0) return 0
    let min = Infinity
    if (n >= 1) {
        min = Math.min(f(n-1) + 1, min)
    }

    if (n >= 5) {
        min = Math.min(f(n-5) + 1, min)
    }

    if (n >= 11) {
        min = Math.min(f(n-11) + 1, min)
    }

    return min
}

console.log(f(15)) // 3

Math.min
min = Math.min(f(n-1) + 1, min)
min = Math.min(f(n-5) + 1, min)
min = Math.min(f(n-11) + 1, min)

遞歸的弊端

我們看似已經把問題解決了,但是別著急,我們繼續測試,當n=70的時候,我們測試要湊出這個數最少我們需要多少個硬幣。

答案是8,但是我們的耗時如下:

如果n=270呢?在八代i7處理器和node.js 12.x版本的加持下我跑了這麼長時間都沒算出來:

當n=27000的時候,我們成功的爆棧了:

所以為什麼會造成如此長的執行耗時?歸根到底是遞歸算法的低效導致的,我們看如下圖:

我們如果計算f(70)就需要分別計算最後一個幣為1、5、11三種面值時的不同情況，而這三種不同情況作為子問題又可以被分解為三種情況，依次類推...這樣的算法複雜度有 O(3ⁿ),這是極為低效的。

我們再仔細看圖:

我們用紅色標出來的都是相同的計算函數，比如有兩個f(64)、f(58)、f(54)，這些都是重複的,這些只是我們整個計算體系下的冰山一角,我們還有非常多的重複計算沒辦法在圖中展示出來。

可見我們重複計算了非常多的無效函數，浪費了算力,到底有多浪費我們已經從上面函數執行時間測試上有了一定的認識。

我們不妨再舉一個簡單的例子，比如我們要計算 「1 + 1 + 1 + 1 + 1 + 1 + 1 + 1」的和。

我們開始數數...,直到我們數出上面計算的和為 8，那麼，我們再在上述 「1 + 1 + 1 + 1 + 1 + 1 + 1 + 1」 後面 「+ 1」，那麼和是多少？

這個時候你肯定數都不會數，脫口而出「9」。

為什麼我們在後面的計算這麼快？是因為我們已經在大腦中記住了之前的結果 「8」，我們只需要計算「8 + 1」即可，這避免了我們重複去計算前面的已經計算過的內容。

我們用的遞歸像什麼？像繼續數「1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1」來計算出「9」，這是非常耗時的。

我們假設用 m 種面值的硬幣湊 n 最少需要多少硬幣，在上述問題下遞歸的時間複雜度是驚人的O(nᵐ),指數級的時間複雜度可以說是最差的時間複雜度之一了。

我們已經發現問題所在了,大量的重複計算導致時間複雜度奇高,我們必須想辦法解決這個問題。

備忘錄與遞歸

既然已經知道存在大量冗餘計算了,那麼我們可不可以建立一個備忘錄,把計算過的答案記錄在備忘錄中,再有我們需要答案的時候,我們去備忘錄中查找,如果能查找到就直接返回答案,這樣就避免了重複計算,這就是算法中典型的空間換時間的思維，我們用備忘錄占用的額外內存換取了更高效的計算。

有了思路後,其實代碼實現非常簡單,我們只需要建立一個緩存備忘錄,在函數內部校驗校驗是否存在在結果,如果存在返回即可。

javascript 代碼展示

function f(n) {
    function makeChange(amount) {
        if(amount <= 0) return 0
    
        // 校驗是否已經在備忘錄中存在結果,如果存在返回即可
        if(cache[amount]) return cache[amount]
    
        let min = Infinity
        if (amount >= 1) {
            min = Math.min(makeChange(amount-1) + 1, min)
        }
    
        if (amount >= 5) {
            min = Math.min(makeChange(amount-5) + 1, min)
        }
    
        if (amount >= 11) {
            min = Math.min(makeChange(amount-11) + 1, min)
        }
    
        return (cache[amount] = min)
    }
    // 備忘錄
    const cache = []
    return makeChange(n)
}
console.log(f(70)) // 8

java 代碼展示

public class Cions {

    public static void main(String[] args) {
        int a = coinChange(70);
        System.out.println(a);
    }
    private static HashMap cache = new HashMap<>();
    public static int coinChange(int amount) {
        return makeChange(amount);
    }
    public static int makeChange(int amount) {
        if (amount <= 0) return 0;

        // 校驗是否已經在備忘錄中存在結果,如果存在返回即可
        if(cache.get(amount) != null) return cache.get(amount);

        int min = Integer.MAX_VALUE;
        if (amount >= 1) {
            min = Math.min(makeChange(amount-1) + 1, min);
        }

        if (amount >= 5) {
            min = Math.min(makeChange(amount-5) + 1, min);
        }

        if (amount >= 11) {
            min = Math.min(makeChange(amount-11) + 1, min);
        }

        cache.put(amount, min);
        return min;

    }
}

我們的執行時間只有:

實際上利用備忘錄來解決遞歸重複計算的問題叫做「記憶化搜索」。

這個方法本質上跟回溯法的「剪枝」是一個目的，就是把上圖中存在重複的節點全部剔除,只保留一個節點即可,當然上圖沒辦法把所有節點全部展示出來,如果剔除全部重複節點最後只會留下線性的節點形式:

這個帶備忘錄的遞歸算法時間複雜度只有O(n),已經跟動態規劃的時間複雜度相差不大了。

那麼這不就可以了嗎？為什麼還要搞動態規劃？

還記得我們上面提到遞歸的另一大問題嗎？

爆棧！

這是我們備忘錄遞歸計算 f(27000) 的結果:

程式語言棧的深度是有限的,即使我們進行了剪枝,在五位數以上的情況下就會再次產生爆棧的情況,這導致遞歸根本無法完成大規模的計算任務。

這是遞歸的計算形式決定的,我們這裡的遞歸是「自頂向下」的計算思路，即從 f(70) f(69)...f(1) 逐步分解,這個思路在這裡並不完全適用,我們需要一種「自底向上」的思路來解決問題。

「自底向上」就是 f(1) ... f(70) f(69) 通過小規模問題遞推來解決大規模問題,動態規劃通常是用疊代取代遞歸來解決問題。

「自頂向下」的思路在另一種算法思想中非常常見,那就是分治算法

除此之外,遞歸+備忘錄的另一個缺陷就是再沒有優化空間了,因為在最壞的情況下，遞歸的最大深度是 n。

因此，我們需要系統遞歸堆棧使用 O(n) 的空間,這是遞歸形式決定的,而換成疊代之後我們根本不需要如此多的的儲存空間,我們可以繼續往下看。

動態轉移方程

還記得上面我們利用備忘錄緩存之後各個節點的形式是什麼樣的嗎,我們把它這個「備忘錄」作為一張表，這張表就叫做 DP table,如下:

注意: 上圖中 f[n] 代表湊夠 n 最少需要多少幣的函數,方塊內的數字代表函數的結果

我們不妨在上圖中找找規律?

我們觀察 f[1] : f[1] = min(f[0], f[-5], f[-11]) + 1

由於 f[-5] 這種負數是不存在的,我們都設為正無窮大,那麼 f[1] = 1 。

再看看 f[5] : f[1] = min(f[4], f[0], f[-6]) + 1 ,這實際是在求 f[4] = 4 、 f[0] = 0 、 f[-6]=Infinity 中最小的值即0，最後加上1，即1，那麼 f[5] = 1 。

發現了嗎？我們任何一個節點都可以通過之前的節點來推導出來，根本無需再做重複計算，這個相關的方程是:

f[n] = min(f[n-1], f[n-5], f[n-11]) + 1

還記得我們提到的動態規劃有更大的優化空間嗎?遞歸+備忘錄由於遞歸深度的原因需要 O(n) 的空間複雜度,但是基於疊代的動態規劃只需要常數級別的複雜度。

看下圖,比如我們求解 f(70),只需要前面三個解,即 f(59) f(69) f(65) 套用公式即可求得,那麼 f(0)f(1) ... f(58) 根本就沒有用了,我們可以不再儲存它們占用額外空間,這就留下了我們優化的空間。

上面的方程就是動態轉移方程,而解決動態規劃題目的鑰匙也正是這個動態轉移方程。

當然,如果你只推導出了動態轉移方程基本上可以把動態規劃題做出來了,但是往往很多人卻做不對,這是為什麼?這就得考慮邊界問題。

邊界問題

部分的邊界問題其實我們在上面的部分已經給出解決方案了,針對這個找零問題我們有以下邊界問題。

處理f[n]中n為負數的問題: 針對這個問題我們的解決方案是凡是n為負數的情況,一律將 f[n] 視為正無窮大,因為正常情況下我們是不會有下角標為負數的數組的,所以其實 n 為負數的 f[n] 根本就不存在,又因為我們要求最少找零,為了排除這種不存在的情況,也便於我們計算,我們直接將其視為正無窮大,可以最大程度方便我們的動態轉移方程的實現。

處理f[n]中n為0的問題： n=0 的情況屬於動態轉移方程的初始條件,初始條件也就是動態轉移方程無法處理的特殊情況,比如我們如果沒有這個初始條件,我們的方程是這樣的: f[0] = min(f[-1], f[-5], f[-11]) + 1 ,最小的也是正無窮大,這是特殊情況無法處理,因此我們只能人肉設置初始條件。

處理好邊界問題我們就可以得到完整的動態轉移方程了:

f[0] = 0 (n=0)
f[n] = min(f[n-1], f[n-5], f[n-11]) + 1 (n>0)

找零問題完整解析

那麼我們再回到這個找零問題中,這次我們假設給出不同面額的硬幣 coins 和一個總金額 amount。編寫一個函數來計算可以湊成總金額所需的最少的硬幣個數。如果沒有任何一種硬幣組合能組成總金額，返回 -1。

比如:

輸入: coins = [1, 2, 5], amount = 11
輸出: 3 
解釋: 11 = 5 + 5 + 1

其實上面的找零問題就是我們一直處理的找零問題的通用化,我們的面額是定死的,即1、5、11，這次是不定的，而是給了一個數組 coins 包含了相關的面值。

有了之前的經驗,這種問題自然就不再話下了,我們再整理一下思路。

確定最優子結構:最優子結構即原問題的解由子問題的最優解構成,我們假設最少需要k個硬幣湊足總面額n,那麼 f(n) = min{f(n-cᵢ)} , cᵢ 即是硬幣的面額。

處理邊界問題:依然是老套路,當n為負數的時候,值為正無窮大,當n=0時,值也為0.

得出動態轉移方程:

f[0] = 0 (n=0)
f[n] = min(f[n-cᵢ]) + 1 (n>0)

我們根據上面的推導,得出以下代碼:

javascript 代碼展示

const coinChange = (coins, amount) => {
  // 初始化備忘錄,用Infinity填滿備忘錄，Infinity說明該值不可以用硬幣湊出來
  const dp = new Array(amount + 1).fill(Infinity)

  // 設置初始條件為 0
  dp[0] = 0

  for (var i = 1; i <= amount; i++) {
    for (const coin of coins) {
      // 根據動態轉移方程求出最小值
      if (coin <= i) {
        dp[i] = Math.min(dp[i], dp[i - coin] + 1)
      }
    }
  }

  // 如果 `dp[amount] === Infinity`說明沒有最優解返回-1,否則返回最優解
  return dp[amount] === Infinity ? -1 : dp[amount]
}

java 代碼展示

class Solution {
    public int coinChange(int[] coins, int amount) {
        // 初始化備忘錄,用amount+1填滿備忘錄,amount+1 表示該值不可以用硬幣湊出來
        int[] dp = new int[amount + 1];
        Arrays.fill(dp,amount+1);
        // 設置初始條件為 0
        dp[0]=0;
        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                // 根據動態轉移方程求出最小值
                if(coin <= i) {
                    dp[i]=Math.min(dp[i],dp[i-coin]+1);
                }
            }
        }
        // 如果 `dp[amount] === amount+1`說明沒有最優解返回-1,否則返回最優解
        return dp[amount] == amount+1 ? -1 : dp[amount];
    }
}

小結

我們總結一下學習歷程：

1. 從貪心算法入手來解決找零問題，發現貪心算法並不是在任何情況下都能找到最優解
2. 我們決定換一種思路來解決存在的問題，我們最終發現了關鍵點,即「最優子結構」
3. 藉助上面的兩個發現，我們用遞歸的方式解決了最少找零問題
4. 但是經過算法複雜度分析和實際測試，我們發現遞歸的方法效率奇低，我們必須用一種方法來解決當前問題
5. 我們用備忘錄+遞歸的形式解決了時間複雜度問題,但是自頂向下的思路導致我們無法擺脫爆棧的陰霾,我們需要一種「自底向上」的全新思路
6. 我們通過動態轉移方程以疊代的方式高效地解出了此題

其實動態規劃本質上就是被一再優化過的暴力破解,我們通過動態規劃減少了大量的重疊子問題,此後我們講到的所有動態規劃題目的解題過程，都可以從暴力破解一步步優化到動態規劃。

本文我們學習了動態規劃到底是怎麼來的，在此後的解題過程中我們如果沒有思路可以在腦子裡把這個過程再過一遍，但是我們之後的題解就不會再把整個過程走一遍了，而是直接用動態規劃來解題。

可能你會問面試題這麼多,到底哪一道應該用動態規劃?如何判斷?

其實最準確的辦法就是看題目中的給定的問題，這個問題能不能被分解為子問題，再根據子問題的解是否可以得出原問題的解。

當然上面的方法雖然準確,但是需要一定的經驗積累,我們可以用一個雖然不那麼準確,但是足夠簡單粗暴的辦法,如果題目滿足以下條件之一,那麼它大機率是動態規劃題目:

• 求最大值，最小值
• 判斷方案是否可行
• 統計方案個數