題目網址：https://leetcode.cn/problems/coin-change-ii/

題意：給一整數 array coins 表示不同面額的硬幣, 和一整數 amount 表示總金額。

返回可以湊成 amount 的硬幣組合數。如果任何硬幣組合都無法湊出總金額, 則返回 0。

假設每一種面額的硬幣有無限個。

題目保證結果符合 32-bit 有號整數。

Solution 1：

想法：利用 DP

1. 定義狀態：

  • 首先, 會在 coins 前先加上一個 0, 代表什麼元素都沒有的狀態
  • dp[i][j]：前 i 種硬幣湊齊金額 j 的組合數

2. 得到轉移方程：

  • coins[i] 有「選 or 不選」兩種可能：
    • rods[i] 不選, 則 dp[i][j] = dp[i - 1][j]
    • rods[i] 要選, 則 dp[i][j] = dp[i][j - coins[i]]（每一種面額可無限取, 故為 i 而非 i - 1）

3. 初始化：

  • dp[0][0]：當沒有任何硬幣時, 湊齊金額 0 的組合數為 1（什麼都不選也是一種方案）
    ➔ dp[0][0] = 1
  • dp[i][0]：當 amount = 0 時, 前 i 種硬幣湊齊金額 j 的組合數為 1（什麼都不選也是一種方案）, 其中 1 ≤ i ≤ n
    ➔ dp[i][0] = 1
  • dp[0][j]：當沒有任何硬幣時, 湊齊金額 j 的組合數為 0, 其中 1 ≤ j ≤ amount
    ➔ dp[0][j] = 0
class Solution {
public:
    int change(int amount, vector<int>& coins) {
        const int n = coins.size();
        vector<vector<int>> dp(n + 1, vector<int>(amount + 1, 0));

        coins.emplace(coins.begin(), 0);

        // 每種硬幣湊齊金額 0 的組合數皆只有一種
        for (int i = 0; i <= n; ++i) {
            dp[i][0] = 1;
        }

        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j <= amount; ++j) {
                if (j >= coins[i]) { // 若金額 ≥ 硬幣面額, 則該種硬幣有取 or 不取兩種選擇
                    dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i]];
                } else { // 若金額 < 硬幣面額, 則該種硬幣只有不取這一選擇
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        return dp[n][amount];
    }
};
  • time：$O(n \cdot amount)$ ➔ for loop, 其中 n 是硬幣種類
  • space：$O(n \cdot amount)$ ➔ dp

Solution 2：

想法：改進 Solution 1, 因為 dp[i][j] 只會用到上一列的狀態, 故只需記住上一列的狀態即可

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int n = coins.size();
        vector<int> dp(amount + 1, 0);

        dp[0] = 1;
        coins.emplace(coins.begin(), 0);

        for (int i = 1; i <= n; ++i) {
            const auto prevRow = dp; // 記住上一列的狀態
            for (int j = 0; j <= amount; ++j) {
                if (j >= coins[i]) { // 若金額 ≥ 硬幣面額, 則該種硬幣有取 or 不取兩種選擇
                    dp[j] = prevRow[j] + dp[j - coins[i]];
                } else { // 若金額 < 硬幣面額, 則該種硬幣只有不取這一選擇
                    dp[j] = prevRow[j];
                }
            }
        }

        return dp[amount];
    }
};
  • time：$O(n \cdot amount)$ ➔ for loop, 其中 n 是硬幣種類
  • space：$O(amount)$ ➔ dp, prevRow

延伸問題：

  • for loop 內、外層能否對調？

    不能, 因為這裡定義的 subproblem 是「選擇第 i 種硬幣時, 湊齊金額 j 的方案（組合數）」。如果對調了, 則 subproblem 就會變成「對於金額 j, 選擇硬幣的方案（排列數）」

    e.g. amount = 3, coins = [1, 2]

    • 內、外層對調後, 會有 1 + 2、2 + 1 這兩種方案