https://leetcode.com/problems/coin-change/description/
You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
Example 1:
Input: coins=[1,2,5], amount=11 Output: 3 Explanation: 11=5+5+1
Example 2:
Input: coins = [2], amount = 3 Output: -1
Note:
You may assume that you have an infinite number of each kind of coin.
You may assume that you have an infinite number of each kind of coin.
中文翻譯:
給你'coins'陣列，代表你有哪些種類的coin可以使用。
然後給你'amount'，代表一個金額。
問你如果要用coins來組成amount，最少可以用幾個coin來表示。
[Solution]
Dynamic Programming.
Solution(amount) is the min of
(solution(amount - coin[1])+1,
solution(amount - coin[2])+1,
,...,
solution(amount - coin[n])+1)
Let's say there are n kinds of coins(idx=1~n), then there are n ways to make up the amount of money.
1.choose a coin[1], and calculate the answer of coinChange(coins, amount-coin[1])
2.choose a coin[2], and calculate the answer of coinChange(coins, amount-coin[2])
3.choose a coin[3], and calculate the answer of coinChange(coins, amount-coin[3])
....
n.choose a coin[n], and calculate the answer of coinChange(coins, amount-coin[n])
In case i, we will get solution of "a coin[i] had been chosen" condition.
So the solution of coinChange(coins, amount) is the minimum of case1~n.
Since some of the answers will be used repeatedly during the procedure, so we should build a dynamic programming table, instead of using recursive function call.
Let's write code.
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
vector<int> dpt(amount+1,-1);//dp table. dpt[i]=solution of amount=i, under 'coins'
dpt[0]=0;//base case
for(int a=1;a<=amount;a++){
//if amount = a
//there are coins.size() ways to make up the amount
// 1.pick coins[0], then calculate solution of amount=a-coins[0]
// 2.pick coins[1], then calculate solution of amount=a-coins[1]
// 3.pick coins[2], then calculate solution of amount=a-coins[2]
// ...total coins.size() cases...
//The min of case 1,2,3,.. will be the solution of amount=a
for(auto c:coins){
if(a-c>=0 && dpt[a-c]!=-1)
dpt[a]=dpt[a]==-1 ? dpt[a-c]+1 : min(dpt[a-c]+1, dpt[a]);
}
}
return dpt[amount];
}
};
