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 forloop 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 kth 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 subarray 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
substructure based on both knapsack capacity and items array (length). if you observe closely, the way
the code is written it does not leverage substructure on items array length. It only uses
the subsstructure 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.