Coin Change
Application of Unbounded Knapsack
-
Algorithms and Data Structures: TheAlgorist.com
-
System Design: www.System.Design
-
Low Level Design: LowLevelDesign.io
-
Frontend Engineering: FrontendEngineering.io
জয় শ্রী রাম
🕉
Problem Statement:
You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin.
Example 1:
Input: amount = 5, coins = [1, 2, 5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
Example 2:
Input: amount = 3, coins = [2]
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.
Example 3:
Input: amount = 10, coins = [10]
Output: 1
Solution:
This problem can be thought of as follows:
- Maximum amount given in this problem is analogous to maximum knapsack weight capacity in the knapsack problem.
- We can use as many instances of each coin as needed. So it is a knapsack problem, it would be Unbounded version of the knapsack problem.
- For every coin we have option to either include that coin (one or more instances) or not include at all.
- All the coins in each combination should make up the exact amount. So it would be similar to filling a knapsack with weight equal to the maximum capacity. If maximum weight capacity of knapsack is W then we would have to put items of weight = W, and any less or more.
From the above discussion it is clear that the given problem can be solved using the concept of Unbounded Knapsack Problem. I have put more details in the inline comments in the code below:
Java Code:
Login to Access Content
Python Code:
Login to Access Content
Space Optimization:
In the above solution we see that dp[current_coin_index][current_amount] depends on dp[current_coin_index - 1][current_amount] and dp[current_coin_index][current_amount - coins[current_coin_index]]. So at any point of time we ony need only rely on
dp[current_coin_index - 1][current_amount]
and
dp[current_coin_index][current_amount - coins[current_coin_index]]
.
So, at any point of time if we are at amount = A and processing coins[i]
we need the "total number of combinations possible for amount = A for coins[0...(i - 1)]"
a "total number of combinations possible for the same coin index coins[0...i] for any amount lesser than current amount".
This means we can start from index 0 of coins array and going computing till index = (n - 1).
For each index we would be computing the the dp values of all possible amounts (0 to max amount).
So if dp[a] gives us the total number of possible combinations for amount = a for certain length of coins[] array, the below code computes the desired result:
for (int len = 1; len <= coins.length; len++) {
for (int weight = 1; weight <= amount; weight++) {
if (weight - coins[len - 1] >= 0) {
dp[weight] += dp[weight - coins[len - 1]];
}
}
}
Below is the complete solution with space optimization:
Java Code:
Please subscribe to access the Code.
After your successful login, please come back and refresh this page.
Python Code:
Login to Access Content
Important note about the nested for-loop in the code above:
If the outer loop is on amount and inner loop on coins that would NOT give correct result, i.e, the below code would give incorrect result:
for (int amt = 1; amt <= amount; amt++) {
for (int len = 1; len <= coins.length; len++) {
if (amt - coins[len - 1] >= 0) {
dp[amt] += dp[amt - coins[len - 1]];
}
}
}
Since in every iteration we are reusing value of dp[j] from previous step,
while computing dp[j] we cannot just use value of dp[j] for coins[0...(n - 1)]
for coin index != (n- 1). If we are counting for k-th coin the value of dp[j]
has to be for coins[0....(k - 1)] and not for the entire coins array. What I mean for this is when we are
computing dp value for subarray weights[0...(k - 1)] we should not involve items from sub-array weights[k...(n - 1)].
The code snippet above does this mistake and consequently it gives wrong answer. An easy way
to figure that the above code snippet won't work is that: from the
problem statement it is clear that the problem has
sub-structure based on both knapsack capacity and items array (length). if you observe closely, the way
the code is written it does not leverage sub-structure on items array length. It only uses
the subs-structure on knapsack capacity.
Tip:
Often times if a problem mentions that you can include an element as many time as you want, or if it specifies that you have infinite number of certain elements, there is a chance that the problem could be solved using
Unbounded
Knapsack Concept.
Instructor:
![](https://thealgoristsblob.blob.core.windows.net/thealgoristsimages/instagram_logo.png)
![](https://thealgoristsblob.blob.core.windows.net/thealgoristsimages/youtube_logo.png)
![](https://thealgoristsblob.blob.core.windows.net/thealgoristsimages/linkedin_logo.png)