Hello everyone,
Can anyone please explain me their approach to this coin change problem
Thank you
I would suggest that you watch this video lecture from Tushar Roy and try to understand. His explanation is pretty neat. In case you have any doubts, you can get them cleared here.
2 Likes
Hint: Suppose you currently have i units of money, and have added j denominations (of infinite count), and you know the number of ways to make change with current configuration in hand. Now, you add another denomination to your collection (making it j+1). Now in how many ways can you construct the change? The answer will at least be the number of ways there were when you had added j-1 denominations and you were adding the jth denomination. What would be extra term? The extra term would be the number of ways of making change in scenario when you had i-c[j+1] units, and you were adding the (j+1)th denomination to your collection!
So our recursive relation becomes dp[i][j+1] = dp[i][j] + dp[i-c[j+1][j+1] (not handling the corner/base cases)
Where dp[i][j+1] means the state where you have i units of money and you have just added the (j+1)th denomination to your collection.
Your final answer is dp[n][m].
A better reference: http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/
1 Like
I’m sorry but what is denomination?
WHy do he go two steps back?
I understand what he’s doing but I’m wondering why he’s going back 2 steps to add.
Denomination of the coin is what characterizes it. Like in a set C = [1,2,4,5], ‘1’, ‘2’, ‘4’, and ‘5’ are denominations. In the problem they use ‘type of coins’ to denote a ‘denomination’.
Language details. Doesn’t affect the algorithm.
Wow you should make a tutorial on this problem, thank you so much for explaining. I was watching youtube tutorials on this problem but they didn’t help, read your approach I understand it now thank you!!
1 Like
Haha thanks 
1 Like