Given a set of coins and a bill value, use minimum number of coins to consist of number.
For example, coin = {1, 2, 5}, bill=11. the minimum coins is 5+5+1=11, 3 coins
coin = {1, 2, 5}, bill=11, the minimum coins is 1+1+1+1+1+1+1+1+1+1+1=11, 11 coins
coin = {2, 5, 7}, bill=11, there is no valid combinations, return -1
coin = {2, 5, 7}, bill=10, minimum is 2+2+2+2+2=10, 5 coins
This problem is DP problem which is quite similar to 0-1 knapsack problem. First of all, we put all coins in coin[] array. The coin should be in ascending order. The formula is below. dp[i][j] means the minimum number of coins when we only use coin[0], coin[1], …, coin[i] to combine bill j.
When j is less than coin[i], then dp[i][j] equals dp[i-1][j]. When j is equal or greater than coin[i], first we use one coin coint[i], then we should find the min number of j-coin[i], whose result we already got and is dp[i][j-coin].
Take coin={1, 2, 5}, bill=11 for example.
The dp array is like below:
So the result is dp[2][11]=3
Take coin={2, 5, 7}, bill=11 for example.
The dp array is like below:
So the result is dp[2][11]=3. Another thing which we should notice is that the number of coins consisting 10 is 2, not -1.
The time complexity O(n*b), space complexity is O(b). n is number of coins, b is bill value.
Here is my code on github: link