指尖劃過的軌跡，藏着最細膩的答案~

題目：

給你一個整數數組 coins ，表示不同面額的硬幣；以及一個整數 amount ，表示總金額。

計算並返回可以湊成總金額所需的 最少的硬幣個數 。如果沒有任何一種硬幣組合能組成總金額，返回 -1 。

你可以認為每種硬幣的數量是無限的。

示例 1：

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

示例 2：

輸入：coins = [2], amount = 3
輸出：-1

示例 3：

輸入：coins = [1], amount = 0
輸出：0

提示：

1 <= coins.length <= 12
1 <= coins[i] <= $2^{31}$ - 1
0 <= amount <= $10^4$

分析：

這是一道揹包問題，由於物品可以無限制使用，即完全揹包問題； 動態規劃一般分為3步走：

• 確定dp數組含義： 設 dp[i][j] 表示使用硬幣i兑換總額為j的最少的硬幣數。
• 狀態轉移方程： 對於每個硬幣i我們可以選擇使用或者選擇不使用，即選或不選，我們可以得到如下狀態轉移方程：
  • 不選：$dp[i][j] = dp[i-1][j]$;
  • 選：$dp[i][j] = min(dp[i-1][j], dp[i][j-coins[i]] + 1)$;
• 初始化： dp[0][0] = 0;

AC代碼：

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int n = coins.size();
        vector f(n + 1, vector<int>(amount + 1, INT_MAX / 2));
        f[0][0] = 0;
        for (int i = 0; i < n; i++) {
            for (int c = 0; c <= amount; c++) {
                if (c < coins[i]) {
                    f[i+1][c] = f[i][c];
                } else {
                    f[i+1][c] = min(f[i][c], f[i+1][c - coins[i]] + 1);
                }
            }
        }

        int ans = f[n][amount];
        return ans < INT_MAX / 2 ? ans : -1;
    }
};

空間複雜度優化算法：

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int n = coins.size();
        vector f(amount + 1, INT_MAX / 2);
        f[0] = 0;
        for (int x : coins) {
            for (int c = x; c <= amount; c++) {
                f[c] = min(f[c], f[c - x] + 1);
            }
        }

        int ans = f[amount];
        return ans < INT_MAX / 2 ? ans : -1;
    }
};