📘 題目敘述
給你一個整數 amount，以及一個整數陣列 coins，表示不同面額的硬幣。
請回傳可以湊出總金額 amount 的「組合數量」。
如果無法湊出該金額，回傳 0。
你可以假設每種硬幣的數量是無限的。
答案保證可以放進 32-bit 有號整數。
條件限制
1 <= coins.length <= 3001 <= coins[i] <= 50000 <= amount <= 5000
🧠 解題思路
這題是典型的「完全背包」組合數 DP。
我用一維 DP step[j] 表示：
湊出金額 j 的組合數量（只使用目前處理到的那些硬幣種類）。
初始化 step[0] = 1，表示湊出 0 元只有一種方式：什麼都不選。
接著我用外層迴圈跑每一種硬幣 i，內層從 j = i 跑到 amount：
step[j] += step[j - i]
意思是：如果我要湊出 j，而且可以用面額 i，那我可以從「先湊出 j - i」的每一種方式後面再加一個 i，就會得到新的方式。
外層先跑硬幣、內層金額由小到大，這個順序能保證我們數到的是「組合」而不是「排列」（不會因為硬幣順序不同而重複計數）。
我用 long long 存 step 是避免中間加總溢位，並且如果超過 INT_MAX 就直接 cap 到 INT_MAX，讓回傳值仍符合題目 32-bit 的保證。
所有變數
step：DP 陣列，step[j]表示湊出金額j的組合數量i：目前處理的硬幣面額j：目前要更新的金額
🪜 主要流程步驟
1. 建立 DP 陣列 step，並初始化 step[0] = 1
我用 step 長度 amount + 1，一開始全部設 0。
把 step[0] = 1，代表湊 0 元只有一種方式。
2. 外層跑硬幣種類，內層跑金額（由小到大）
對每個硬幣面額 i：
我讓 j 從 i 走到 amount：
step[j] += step[j - i]
代表把所有「湊出 j-i 的方法」延伸成「湊出 j 的方法」。
3. 用 INT_MAX 封頂，避免 long long 結果太大
題目說答案一定在 32-bit 內，但中間加總我還是用 long long 存。
如果 step[j] > INT_MAX，我就把它設成 INT_MAX，讓回傳值不會爆掉。
4. 回傳 step[amount]
最後 step[amount] 就是湊出 amount 的組合數量。
⏱️ 複雜度
- 時間複雜度：
O(amount * coins.length)每個硬幣都要更新一次 0..amount 的 DP。 - 空間複雜度：
O(amount)只用一個長度amount + 1的一維 DP。
💻 程式碼實作
class Solution {
public:
int change(int amount, vector<int>& coins) {
vector<long long> step(amount + 1, 0);
step[0] = 1;
for (int i : coins) {
for (int j = i; j <= amount; j++) {
step[j] += step[j - i];
if (step[j] > INT_MAX) {
step[j] = INT_MAX;
}
}
}
return step[amount];
}
};