518. Coin Change 2

──────────────────────────────────────────────────────────────────────

518. Coin Change 2

給定硬幣面額和目標金額，問湊出目標金額總共有幾種組合 —— 只看每種面額各用了幾枚，不看順序。

思路

這個題目是 322 Coin Change 的進階題目，該題是個動態規劃的問題，目標是要找到使用最少的硬幣組合，而這道題目並不要求找到最少的硬幣，而是要找出總共有幾種組合，這個題目就變成了一個窮舉的題目。

但是這個裡面的窮舉，只在乎某個面額的硬幣，總共使用了幾枚，並不在乎到底是用什麼數量排出的，例如當硬幣的面額有 [1, 2] 兩種，目標是要找到 5 元的硬幣，[1, 2, 2], [2, 2, 1] 這兩種組合都是使用一枚一元、兩枚兩元，並不重複計算。

這也就是這個題目比較困難的地方。

既然是要窮舉，Backtracking 應該是最適合的，但是 Backtracking 會把各種排列組合都計算進去，當然可以透過一些方法在窮舉時排除掉重複的情況，但是多會增加時間複雜度。
雖然是窮舉，但是我們可以把以上出現重複的組合，視為重複的子問題，也就是說如果我們知道怎麼樣的情況會是重複的子問題，就可以把窮舉改寫成動態規劃的表達式。

觀察窮舉的過程

這時候可以先觀察這個題目窮舉的過程

在選硬幣的過程中，可以把能選用的硬幣依照幣值大小排列好。
如果從幣值最小的先選，通常可以選出最多枚，接著拿出部分最小值的硬幣，以面額次小的硬幣取代掉，不斷的重複這個過程，就可以知道最後有哪些組合了。
如果從幣值最大的先選，通常會選出最少枚硬幣，接著每次拿出面額最大的硬幣，用面額次大的硬幣取代，不斷的重複這個過程，就可以知道最後有哪些組合了。

從上述的過程中，不管是從面額小的開始去選擇，還是從面額大的去選擇，基本上都可以找出答案，其中最重要的一個點就是，從當前的面額來看時，要往一個恆定的方向去找，那就是只能朝面額更大的方向去找，或是朝面額更小的地方去找。

這樣的方式可以很有系統性地去找出所有的組合，不過這裡有一個但書，那就是題目並沒有告訴我們說所有的硬幣是依序排列的，所以透過上述的觀察，我們需要多做一個排序來完成我們的演算法。

排序有必要嗎

這個題目其實存在著不需要先排序過的答案，但是我覺得面試時有著上述的觀察其實並沒有什麼不對，沒有寫過題目的人本來就會需要先透過觀察來完成題目的需求。

只是這裡存在著一個討論，那就是排序到底是有沒有必要的？例如：題目給定了 [2, 1, 5] ，那是不是可以先把 2 給利用完了後，再開始看 1 呢？其實仔細想一下，這完全是沒有問題的，因為其實這個題目的精髓是慢慢地取代掉面額，因此只要嚴格地從當前的位置選出要多少個，並且剩下的面額都是從右方的面額選取，那就依然可以窮舉出所有的選擇。排序其實只是方便人類去思考，對於電腦來說，這樣的記憶量是很輕鬆的。

這樣其實我們就可以完成動態轉移方程了。

解題方向

自頂向下

dfs(remaining, index) 的定義是：只准用 coins[index:] 這些面額，湊出 remaining 有幾種組合。設總共有 n 種面額：

f (r e m a i n i n g, i n d e x) = \sum_{i = i n d e x}^{n - 1} f (r e m a i n i n g - c o i n s [i], i)

邊界有兩條：f(0, index) = 1，湊剛好就是一種湊法；remaining < 0 時回傳 0，代表這條路走不通。

式子裡有兩個地方是這題的關鍵，剛好對應上面觀察到的兩件事：

i 從 index 開始而不是從 0 開始 —— 這就是「只能朝一個恆定的方向去找」，不回頭就不會把 1+2+2 和 2+2+1 數成兩種
遞迴傳下去的是 i 而不是 i + 1 —— 同一種面額可以再拿一枚

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        
        @cache
        def dfs(remaining, index):
            if remaining < 0:
                return 0
            if remaining == 0:
                return 1

            count = 0
            for i in range(index, len(coins)):
                coin = coins[i]
                count += dfs(remaining - coin, i)
            return count
        
        return dfs(amount, 0)

自底向上

dp[i] 的定義是：湊出金額 i 有幾種組合。

不過一維的樣子是壓縮過的，先把二維寫出來比較好懂。令 dp[j][i] 是「只用前 j 種硬幣、湊出金額 i 的組合數」，第 j 種硬幣的面額寫成 $c o i n_{j}$ ：

d p [j] [i] = d p [j - 1] [i] + d p [j] [i - c o i n_{j}]

dp[j-1][i] —— 不用第 j 種硬幣，那答案就跟只有前 j-1 種時一樣
dp[j][i - coin_j] —— 用掉一枚第 j 種硬幣。注意這裡還是 j 不是 j-1，因為同一種硬幣可以再拿

邊界是 dp[j][0] = 1：湊出 0 元有一種方法，就是什麼都不拿。這是整張表唯一的 1，其他所有數字都是從它一路加回來的。

程式碼裡的一維 dp 就是把 j 這個維度滾掉：外層 for coin in coins 走的就是 j，dp 每跑完一輪就地變成「多考慮了這一種硬幣」的版本。所以 dp[i] += dp[i - coin] 讀起來就是上面那條式子 —— 等號左邊被加的舊值是 dp[j-1][i]，加上去的是 dp[j][i - coin]。

兩層迴圈的順序不能對調。 外層硬幣、內層金額算的是組合；對調成外層金額、內層硬幣，算出來的會是排列：

amount / coins	這裡的寫法	對調之後
5 / `[1, 2, 5]`	4	9
10 / `[2, 3, 5]`	4	14
8 / `[1, 2, 3]`	10	81

對調之後那一欄正好是「377. Combination Sum IV」要的答案，因為外層變成金額之後，每個金額都會把所有面額再問一次，1+2+2 和 2+2+1 就被分開數了。這也就是思路裡說的「要往一個恆定的方向去找」—— 那個方向在這裡就是外層迴圈。

內層必須從小到大。 dp[i - coin] 在同一輪裡已經被更新過，代表「這種硬幣可以再拿一枚」。如果內層改成從大到小，dp[i - coin] 讀到的還是上一輪的值，每種硬幣就只能用一次 —— 那是 0/1 背包，也就是 416. Partition Equal Subset Sum 的形狀。上面那三筆測資倒著跑會變成 1、1、0。

至於外層硬幣本身的先後順序，一樣是無所謂的 —— 和上面「排序有必要嗎」那段的結論一致，coins 有沒有排序、怎麼排，答案都相同。

整理見 Dynamic Programming 模板裡「兩層迴圈的順序決定題型」那段。

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [0] * (amount + 1)
        dp[0] = 1

        for coin in coins:
            for i in range(coin, amount + 1):
                dp[i] += dp[i - coin]
        return dp[amount]

複雜度

設 amount 是目標金額、n 是硬幣的種類數。

自頂向下

時間 $O (a m o u n t \times n^{2})$ — 狀態是（剩餘金額, 從哪個面額開始選），共 $O (a m o u n t \times n)$ 個，而每個狀態裡的迴圈最多跑 n 次
空間 $O (a m o u n t \times n)$ — cache 的大小；另外遞迴深度是 $O (a m o u n t)$ ，一路都選最小面額的時候最深

自底向上

時間 $O (a m o u n t \times n)$ — 就是兩層迴圈，外層 n 種硬幣、內層 amount 格
空間 $O (a m o u n t)$ — 只有一維的 dp

兩者差了一個 n，差別在於自頂向下每個狀態都要重跑一次「從 index 開始的每種面額」，而自底向上把「這一種面額」提到外層迴圈，一種只處理一次。