This question seems to be very easy at first sight and the solution also comes up to mind, but believe me, you are going to guess it wrong if you are not familiar with Dynamic Programming. I also tried the first solution that came up to mind and that was the wrong one. I have mentioned the first and the correct solutions in this article.
Difficulty: Medium
Jump To:
Problem Statement
Question: https://leetcode.com/problems/coin-change/
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
.
You may assume that you have an infinite number of each kind of coin.
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
Example 3:
Input: coins = [1], amount = 0
Output: 0
Example 4:
Input: coins = [1], amount = 1
Output: 1
Example 5:
Input: coins = [1], amount = 2
Output: 2
Constraints:
-
1 <= coins.length <= 12
-
1 <= coins[i] <= 231 - 1
-
0 <= amount <= 104
Explanation
The problem is simple and relatable, we just need to break an amount into the change based on the coins we have, the special thing is that the number of coins in the change should be minimum i.e. there should not be any combination of coins available which has the number of coins less than your answer.
Solution
So the first solution that came up in my mind was a greedy approach that I will sort the coins in descending order based on their values and try to include the biggest coin because it will decrease the amount by a bigger value and that can be filled by smaller coins so I'll get the minimum number of coins solution. Like as in Example 1: coins = [1,2,5], amount = 11
so the sorted coins will be [5,2,1]
now I'll include 5
first which results in 2 coins, and the rest amount is 11 - (5x2) = 1
which can be fulfilled by 1
coin so I'll be using 3
coins total. The code is below:
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
int ans=0;
sort(coins.begin(), coins.end(), greater<int>());
auto ptr = coins.begin();
while(amount && ptr!=coins.end()){
if(amount >= (*ptr)){
ans += (amount/(*ptr));
amount %= (*ptr);
}
ptr++;
}
return amount ? -1 : ans;
}
};
BUT
BUT
BUT
This is not a correct solution, Let's look at a beautiful case coins=[9,6,5,1], amount=11
. If I include 9
then the rest value is 2
which can be created by 2 1
coins, in this way I'll be using 3 coins
but the correct solution is 2 coins
which can be achieved using 2 coins 5 & 6
.
So what should be the correct solution???
So let's understand the correct solution now. The problem occurred when we included the big element first what if we go for the solution in a subproblem manner? I mean let's try to achieve the solution for amount=1
, then for amount=2
then for amount=3
, and so on until we get the solution for the amount we want. The interesting thing in this is that whenever I'm trying to get the solution for n
, I already have the solution for all the values below n
which can be used.
Did you ask, how? So, let's understand that in this way, I will try to include each coin to make a value equals to the current amount
, If I am able to include this coin then check if including this coin results in the minimum number of coins till now if yes then I'll include this coin else not. Now here this past data will help. We'll understand this with an example but before that let's see the algorithm first.
Algorithm:
- Create an array
dp
to keep track of all the solution from0
toamount
- Fill this array with Maximum Value of
Integer
- For
amount=0
we need0
coins so setdp[0]=0
- Now fill the array using the below loop from
i=1
to theamount
- Try each coin one by one to create amount
i
using this coinj
- If the value of this coin is smaller or equal to
i
then do below else pick the next coin - If this coin is included then the rest of the amount is
i-coins[j]
- Now check if a solution exists for this amount i.e.
dp[i-coins[j] != INT_MAX
and including this coins gives better solution then the current one - If yes then include this coin and replace
dp[i]
with new minimum valuedp[i-coins[j] + 1
- If the value of this coin is smaller or equal to
- Try each coin one by one to create amount
- If
dp[amount]=INT_MAX
i.e there is no solution so return-1
else returndp[amount]
Time Complexity: O(amount * coins.length)
Space Complexity: O(amount)
Explanation of solution with an example:
Let's see this with the above example.
coins = [9, 6, 5, 1]
amount = 11
Below is the dp
array after step-3:
Dynamic Array | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
dp: | 0 | INT_MAX | INT_MAX | INT_MAX | INT_MAX | INT_MAX | INT_MAX | INT_MAX | INT_MAX | INT_MAX | INT_MAX | INT_MAX |
Below is the screenshot of above dp
array at various stage of the algorithm:
Dynamic Array | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
i=1 | j=3 | coins[j]=1 | ||||||||||
dp: | 0 | 1 | INT_MAX | INT_MAX | INT_MAX | INT_MAX | INT_MAX | INT_MAX | INT_MAX | INT_MAX | INT_MAX | INT_MAX |
i=2 | j=3 | coins[j]=1 | ||||||||||
dp: | 0 | 1 | 2 | INT_MAX | INT_MAX | INT_MAX | INT_MAX | INT_MAX | INT_MAX | INT_MAX | INT_MAX | INT_MAX |
i=5 | j=1 | coins[j]=5 | ||||||||||
dp: | 0 | 1 | 2 | 3 | 4 | 1 | INT_MAX | INT_MAX | INT_MAX | INT_MAX | INT_MAX | INT_MAX |
i=6 | j=1 | coins[j]=5 | ||||||||||
dp: | 0 | 1 | 2 | 3 | 4 | 1 | 2 | INT_MAX | INT_MAX | INT_MAX | INT_MAX | INT_MAX |
i=6 | j=2 | coins[j]=6 | ||||||||||
dp: | 0 | 1 | 2 | 3 | 4 | 1 | 1 | INT_MAX | INT_MAX | INT_MAX | INT_MAX | INT_MAX |
i=11 | j=0 | coins[j]=9 | ||||||||||
dp: | 0 | 1 | 2 | 3 | 4 | 1 | 1 | 2 | 3 | 1 | 2 | 3 |
i=11 | j=1 | coins[j]=5 | ||||||||||
dp: | 0 | 1 | 2 | 3 | 4 | 1 | 1 | 2 | 3 | 1 | 2 | 2 |
-
i=1, j=3, coins[j]=1:
amount=1
can be achieved by using 11
coin sodp[1]
becomes1
-
i=2, j=3, coins[j]=1:
amount=2
can be achieved by using 21
coins sodp[2]
becomes2
-
i=5, j=1, coins[j]=5:
amount=5
can be achieved by using 51
coins but using 15
coin is better solution asrest = dp[5 - 5] = 0
so using current coin5
means we will be using0+1=1
coin sodp[5]
becomes1
-
i=6, j=1, coins[j]=5:
amount=6
can be achieved by using5
coin asrest = dp[6 - 5] = 1
so using current coin5
means we will be using1+1=2
coin sodp[6]
becomes2
-
i=6, j=2, coins[j]=6:
amount=6
can be achieved by using6
coin and it's a better solution asrest = dp[6 - 6] = 0
so using current coin6
means we will be using0+1=1
coin and it's lesser than current solutiondp[6]=2
sodp[6]
becomes1
-
i=11, j=0, coins[j]=9:
amount=9
can be achieved by using coin9
asrest = dp[11 - 9] = 2
so using current coin9
means we will be using2+1=3
coin sodp[11]
becomes3
-
i=11, j=1, coins[j]=5:
amount=11
can be achieved by using coin5
as well and it's a better solution asrest = dp[11 - 5] = dp[6] = 1
so using current coin5
means we will be using1+1=2
coin and it's lesser than current solutiondp[11]=3
sodp[11]
becomes2
Implementation
C++ Code:
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
// Initialize DP array with INT_MAX and dp[0]=0
int dp[amount+1];
dp[0]=0;
for(int i=1;i<=amount;++i)
dp[i] = INT_MAX;
int len = coins.size();
// Fill DP array from amount=1 to amount's actual value
for (int i = 1; i <= amount; ++i)
{
// Try to include all the coins one by one
for (int j = 0; j < len; ++j)
{
// If this coin is usable(value less than current amount)
if(coins[j] <= i){
// What is the cost for rest of the amount
// If I use this coin
// eg. if amount=8 and coins[j]=5 then rest is min cost
// for 8-5 = 3
int rest = dp[i-coins[j]];
// If including this coin gives lesser value
// than current min value then include it
if(rest != INT_MAX && rest+1<dp[i]){
// update min value for amount=i
dp[i] = rest+1;
}
}
}
}
return dp[amount]==INT_MAX ? -1 : dp[amount];
}
};
Runnable C++ Code:
Cover Photo by Marc Schaefer on Unsplash
Top comments (1)
Thanks for the explanation. I'll admit, this one had me stumped. My initial solution was the same approach as yours, and when I ran the 3 examples they provided and it worked, I thought "That was easy!"... Then when I realized why it wasn't correct, I couldn't come up with another solution with reasonable complexity.
Here it is in Rust, if anyone is interested: