LeetCode | 518 Coin Change II

今天打開 leetcode，點進去它推送的 daily challenge，然後就成為了今天噩夢的開始...我要好好了解演算法了 QQ

舉例來說，就是如果有 1、2、5 三種面額的硬幣，要湊成 5 元可以有幾種湊法，答案是 4 種：

from: LeetCode

不難理解題目的意思吧。然後真的開始寫就爆炸了，我的 code 歷經了多輪測試層層挺進，最後死在了要用 1、2、5 去湊出 500 元來，給大家看一下有多慘哈...

所以我忍不住了，直接點開 solutions 看大神怎麼解，然後歪唷，嗯，看某...還跑去問了 ChatGPT 才知道這用的是動態規劃的解法，而這題也是動態規劃的經典題。經典是經典，但為難了我這還沒出新手村的孩砸...。

Code 是這樣子的：

var change = function(amount, coins) {
    const dp = new Array(amount + 1).fill(0);
    dp[0] = 1;

    for (const coin of coins) {
        for (let i = coin; i <= amount; i++) {
            dp[i] += dp[i - coin];
        }
    }

    return dp[amount];
}

一個陣列、兩個迴圈，簡簡單單，然後我跟 ChatGPT 拉扯了幾個小時、爬了幾篇動態規劃的文章，後來在中午吃飯時看了下面兩部影片才算是稍微知道這串 code 背後的邏輯思維是啥。我就稍微記錄一下我的理解哈，如果有理解錯拜託小力鞭 QQ

所以這串 code 到底搞了什麼事情，我嘗試理解拆解了一下。

1.) 建立了一個長度為 amount + 1 的陣列 "dp"，它是用來儲存湊成金額 "i" 的方法數量的陣列。因為還沒開始更新，所以先把值都設為 0。

好了，為何要一個個把金額 i 列出來？題目不是只要求要湊到 amount 就好嗎？我後來理解這就是有關動態規劃的 "把大問題拆成很多小問題，然後由小問題的解組合成大問題的解" 的概念所在，很渾沌對吧？用下面例子說應該會比較清楚一點...

2.) 先建立了一個陣列後，把 dp[0] 設為 1，這裡的意思很簡單，就是湊成金額 0 的方法只有一個，就是都不拿任何硬幣。

3.) 開始第一遍遍歷 (coin = 1)，我們計算出使用硬幣面額 1 去湊出目標金額 i (1 ~ 5) 的方法有幾種。答案是都是一種，因為 "1 = 1"、"2 = 1 + 1"、"3 = 1+ 1 + 1"...以此類推，到這裡都還不難理解齁。

4.) 第二遍遍歷 (coin = 2)，噩夢的開始，天知道我花了多久在思考這裡。我們先再看一次內層的迴圈。

for (let i = coin; i <= amount; i++) {
            dp[i] += dp[i - coin];
        }

可以知道我們硬幣 2 要從目標金額 2 (i = 2) 開始湊了。但為什麼是dp[i] += dp[i - coin]？

先再重申一次 dp[i] 是儲存湊成 i 金額方法數的地方，所以 dp[2] 就是儲存湊成 2 的方法數的地方，再一次強調，免得待會打結。

好，現在來看一下下面這張圖，我用紅色和藍色分別標記了兩個 1，是什麼意思？是這樣的：

• 紅色的 1：dp[2] 在第一次遍歷時，也就是 coin = 1 時所儲存的方法數，也就是 "1 + 1" 這個組合。
• 藍色的 1：dp[2] 在第二次遍歷時，也就是 coin = 2 時所要更新儲存進去的方法數。我們知道也就是只取 2 這一個方法，但我們應該想成 "0 + 2" 這個組合，而我們有沒有湊成 0 的方法數？答案是有的，在一開始就定義了，也就是 1。

我們接著看 dp[3]：

• 紅色的 1：在第一次遍歷時儲存了一個方法，也就是 "1 + 1 + 1"。
• 藍色的 1：到了第二次遍歷時，我們多出了 "1 + 2" 這個組合，而湊成 1 的方法數到目前為止是 1。

dp[3]

再一次啊，來看 dp[4]：

• 紅色的 1：在第一次遍歷時儲存了只用 coin = 1 的方法，也就是 "1 + 1 + 1 + 1"。
• 藍色的 2：哇！變成 2 了，怎麼不是 1 了？其實按照剛剛的邏輯來看，我們用 coin = 2 要湊 i = 4 時，會得到 "2 + 2" 這個組合，那我們前面已經存過截至目前為止所儲存可以湊出 2 的方法數有 2 個，也就是 coin = 1 時儲存的 "1 + 1" 和迴圈才剛剛跑過去沒多久的 "0 + 2"

dp[4]

所以到這裡可以知道dp[i] += dp[i - coin]這裡面dp[i]代入的是前一次遍歷更新後湊成 i 的方法數，dp[i - coin]代表著使用了一次這個硬幣後，我們還需要湊成剩餘金額 "i - coin" 的湊法數量，而這個數量我們已經在前面的迴圈中儲存在 dp 中了。

到這裡我們可以看到，每次代入的參數其實都是前一次遍歷和迴圈帶來的結果，這樣一層一層堆砌成最後的解答，動態規劃的概念這就出現了。

最後我們會得到下面這張圖，也就是此時 dp = [1, 1, 2, 2, 3, 4]。而 4 就是我們最終的解答。

e04！真的搞了我好久，我要好好去學演算法了...

參考資料：

1. 贾考博 LeetCode 518. Coin Change 2 - 这应该是hard
2. LeetCode 518 Coins Change II解题分享 DP