2

# 換零錢(一)- 最少要幾個硬幣湊n元?

Input: coins = [1, 2, 5], amount = 11
Output: 3

DP[i]= min(DP[i-1], DP[i-2], DP[i-5])+1
(general的情況請自行類推)

## c++ 程式

class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
long long inf = (long long)1<<32;
vector<long long> DP(amount+1, inf);
DP[0]=0;
int min_coin = coins[0];
for(int i = 1; i<coins.size(); i++){
min_coin = min(coins[i], min_coin);
}
for(int i = min_coin; i<= amount; i++){
long long min_way = inf;
for(int coin: coins){
if(i-coin>=0){
min_way = min(min_way, DP[i-coin]);
}
}
DP[i] = min_way+1;
}
return DP[amount]<inf?DP[amount]:-1;
}
};

## python 程式 (我感覺此題python較容易寫)

class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
DP = [0] + [float('inf')] * amount
for i in range(min(coins), amount+1):
DP[i] = min([DP[i-x] for x in coins if i-x>=0])+1
return DP[-1] if DP[-1]!=float('inf') else -1

# 換零錢(二)- 總共有幾種方式湊n元?

Input: amount = 5, coins = [1, 2, 5]
Output: 4

5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

• 不使用第i種錢，共DP[i-1][j]種可能
• 在「第i種錢的幣值<=j的狀況下可以用第i種錢」，共DP[i][j-第i種錢的幣值]種可能

## c++ 程式

class Solution {
public:
int change(int amount, vector<int>& coins) {

//DP[i][j]表示使用前i種銅版，湊j元有幾組解
vector<vector<int>> DP(coins.size()+1, vector<int>(amount+1,0));

for(int i=0;i<DP.size();i++){
DP[i][0] = 1; //湊0元都是一種方法
}

for(int i=1;i<DP.size();i++){
for(int j=1;j<DP[0].size();j++){
DP[i][j] = DP[i-1][j] + (coins[i-1]<=j?DP[i][j-coins[i-1]]:0);
}
}
return DP[coins.size()][amount];

}
};

## python 程式

class Solution:
def change(self, amount: int, coins: List[int]) -> int:
# DP[i][j]表示使用前i種銅版，湊j元有幾組解
DP = [[0]*(amount+1) for i in range(len(coins)+1)]

for i in range(len(DP)):
DP[i][0] = 1; #湊0元都是一種方法

for i in range(1, len(DP)):
for j in range(1, len(DP[0])):
DP[i][j] = DP[i-1][j] + (DP[i][j-coins[i-1]] if coins[i-1]<=j else 0);
return DP[len(coins)][amount];

<另解>

## c++ 程式

class Solution {
public:
int change(int amount, vector<int>& coins) {

vector<int> DP(amount+1,0); //DP[i]湊i元有幾組解
DP[0] = 1; //湊0元為一種方法
for(int coin: coins){
for(int i=0; i<=amount;i++){
if(i-coin>=0){
DP[i] += DP[i-coin];
}
}
}
return DP[amount];
}
};

## python 程式

class Solution:
def change(self, amount: int, coins: List[int]) -> int:
DP = [1] + [0] * amount # DP[i]表示湊i元有幾組解(湊0元有一組解)
for coin in coins:
for i in range(amount+1):
if i-coin>=0:
DP[i] += DP[i-coin]
return DP[amount]