PROBLEM LINK:
Author: Shivani Srivastava
Tester: Shivani Srivastava
Editorialist: Kaushambi Gujral
DIFFICULTY:
Medium
PREREQUISITES:
Dynamic Programming
PROBLEM:
Given a set of coins and notes as well as some amounts, we have to find out the number of coins/notes required to make up those amounts.
QUICK EXPLANATION:
Use DP to form a solution matrix. Use the formula as given below in the explanation. The last element of the solution matrix contains the answer.
EXPLANATION:
When one looks at the problem, it seems easy. The most instinctive approach is that of using recursion. But, if you solve it using the same, chances are that you’ll end up
with T.L.E. The reason is that this approach takes 2^n time, which is huge. For every coin/note, we have 2 options- either we include it or exclude it.
If we think in terms of binary,
its 0(exclude) or 1(include). For example, if we have 2 coins, the options will be 00, 01, 10, 11. So, it’s 2^2. For n coins , it will be 2^n. In all these options we will be checking
whether that selection has made the change which is required.If we notice that we are solving many sub-problems repeatedly, we can do better by applying Dynamic Programming.
Create a solution matrix. (solution[coins+1][amount+1]).
Base Case:
if amount=0 then just return empty set to make the change, so 1 way to make the change.
Rest of the cases:
For every coin/note we have an option to include or exclude it in the solution matrix.
Check if the coin value is less than or equal to the amount needed, if yes then we will find ways by including and excluding that coin/note.
Include the coin/note: reduce the amount by coin/note value and use the sub problem solution (amount-v[i]).
Exclude the coin/note: solution for the same amount without considering that coin/note.
If coin/note value is greater than the amount, then we can’t consider it. The solution will be without that coin/note.
To summarize:
solution[i][j] =
0 ;if i=0
1 ;if j=0
solution[i — 1][j] + solution[i][j — v[i — 1]] ;if(coin[i]<=j)
solution[i — 1][j] ;if(coin[i]>j)
The last element of the solution matrix contains the answer.
AUTHOR’S AND TESTER’S SOLUTION:
The solution can be found here.