coins = [1,2,5] 代表 面額為1,2,5的硬幣，求組合的加總為amount所需的最小硬幣數。
Python
dp求解 :
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
dp = [amount+1]*(amount+1)
dp[0] = 0
for i in range(1,amount+1):
for coin in coins:
if i-coin>=0:
dp[i] = min(dp[i-coin]+1,dp[i])
return dp[amount] if dp[amount]!=(amount+1) else -1 Ｃ＋＋
首先定義了一個Solution類，它包含一個公共的函數coinChange，這個函數接受一個整數數組coins和一個整數amount作為參數，返回使得金額amount能夠被硬幣數組coins中的硬幣組合成的最小硬幣數。在coinChange函數中，我們首先定義一個大小為amount+1的vector dp，dp[i]表示湊成金額i需要的最小硬幣數。
接下來，我們初始化dp[0] = 0，表示湊成金額0需要的最小硬幣數為0。然後，我們使用一個雙重循環遍歷硬幣數組coins和所有的金額i，計算dp[i]的值。
對於每個金額i，我們遍歷硬幣數組coins，對於每個硬幣coins[j]，如果coins[j] <= i，表示當前的硬幣coins[j]可以使用，我們嘗試使用coins[j]去湊成金額i，那麼需要的最小硬幣數為dp[i-coins[j]] + 1，即湊成金額i-coins[j]需要的最小硬幣數加上當前使用的硬幣coins[j]，我們將這個值與當前的dp[i]比較，取較小值作為dp[i]的值。
最後，我們返回dp[amount]的值，如果dp[amount] > amount，表示無法湊成金額amount，返回-1，否則返回dp[amount]。
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
// 初始化dp
vector<int> dp(amount+1, amount+1);
dp[0] = 0;
// 動態規劃
for (int i = 1; i <= amount; i++) {
for (int j = 0; j < coins.size(); j++) {
if (coins[j] <= i) {
dp[i] = min(dp[i], dp[i-coins[j]] + 1);
}
}
}
return (dp[amount] > amount) ? -1 : dp[amount];
}
};