題目描述：

給你一個整數數組 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³¹ - 1
0 <= amount <= 10⁴

題解：

解題思路：

思路一（動態規劃）：

1、通過題目的描述需解決湊成總金額所需的最少的硬幣個數，且硬幣可以重復使用，這樣自然而然將問題轉換為了完全背包問題（金幣的數量為物品的個數，金額為物品的價值）。

2、具體思路如下：
① dp[j],dp數組的含義為：放滿j容量的背包，最少的物品數量。
② dp[j]=min(dp[j],dp[j-nums[i]]+1) ，等號右側 dp[ j ]代表不放物品 i ， dp[j-nums[i]]+1 代表放物品 j 。
③ dp[0]=0,因容量為 0 的背包可以放 0 件物品
④ 因取最小值，其他的dp數組的元素值為INT_MAX，數以這里需考慮溢出的情況dp[j-nums[i]]若為INT_MAX再加一則會溢出
⑤ 因可重復使用同一金額的硬幣則遍歷順序為從左到右。

3、復雜度分析：
① 時間復雜度：O(Sn)，其中 S 是金額，n 是面額數（物品的價值）。我們一共需要計算 O(S) 個狀態，S 為題目所給的總金額（背包容量）。雙重循環遍歷 物品 和 背包。

② 空間復雜度：O(S)。dp 所需的空間 。

代碼實現

代碼實現（思路一（動態規劃））：

class Solution{
public:// 定義 coinChange 函數，參數為硬幣面值數組 coins 和目標金額 amountint coinChange(vector<int> &coins, int amount){// 初始化 dp 數組，大小為 amount + 1（從 0 到 amount），并將所有元素初始化為 INT_MAX// dp[i] 表示湊成金額 i 所需要的最少硬幣數量vector<int> dp(amount + 1, INT_MAX);// dp[0] = 0，因為湊成金額 0 不需要任何硬幣dp[0] = 0;// 外層循環遍歷每種硬幣（物品）for (int i = 0; i < coins.size(); i++){// 內層循環遍歷從當前硬幣面值到目標金額之間的所有金額（背包）for (int j = coins[i]; j <= amount; j++){// 防止數據溢出：只有當 dp[j - coins[i]] 不等于 INT_MAX 時，才進行更新// 這是因為如果 dp[j - coins[i]] 為 INT_MAX，表示無法湊成金額 j - coins[i]if (dp[j - coins[i]] != INT_MAX) {// 更新 dp[j]：表示使用當前硬幣后，湊成金額 j 的最小硬幣數dp[j] = min(dp[j], dp[j - coins[i]] + 1);}}}// 如果 dp[amount] 還是 INT_MAX，表示無法湊成目標金額，返回 -1// 否則返回 dp[amount]，即湊成目標金額所需要的最少硬幣數量return dp[amount] == INT_MAX ? -1 : dp[amount];}
};

以思路一為例進行調試

#include<iostream>
#include<vector>
using namespace std;class Solution{
public:// 定義 coinChange 函數，參數為硬幣面值數組 coins 和目標金額 amountint coinChange(vector<int> &coins, int amount){// 初始化 dp 數組，大小為 amount + 1（從 0 到 amount），并將所有元素初始化為 INT_MAX// dp[i] 表示湊成金額 i 所需要的最少硬幣數量vector<int> dp(amount + 1, INT_MAX);// dp[0] = 0，因為湊成金額 0 不需要任何硬幣dp[0] = 0;// 外層循環遍歷每種硬幣（物品）for (int i = 0; i < coins.size(); i++){// 內層循環遍歷從當前硬幣面值到目標金額之間的所有金額（背包）for (int j = coins[i]; j <= amount; j++){// 防止數據溢出：只有當 dp[j - coins[i]] 不等于 INT_MAX 時，才進行更新// 這是因為如果 dp[j - coins[i]] 為 INT_MAX，表示無法湊成金額 j - coins[i]if (dp[j - coins[i]] != INT_MAX) {// 更新 dp[j]：表示使用當前硬幣后，湊成金額 j 的最小硬幣數dp[j] = min(dp[j], dp[j - coins[i]] + 1);}}}// 如果 dp[amount] 還是 INT_MAX，表示無法湊成目標金額，返回 -1// 否則返回 dp[amount]，即湊成目標金額所需要的最少硬幣數量return dp[amount] == INT_MAX ? -1 : dp[amount];}
};int main(int argc, char const *argv[])
{// 給定硬幣面值數組和目標金額vector<int> coins = {1, 2, 5};int amount = 11;// 創建 Solution 對象Solution s;// 調用 coinChange 函數并輸出結果cout << s.coinChange(coins, amount);return 0;
}

LeetCode 熱題 100_零錢兌換（85_322)原題鏈接
歡迎大家和我溝通交流(????)