Coin Changing Minimum Coins Dynamic Programming

Given set of coins of unlimited quantity and a total. How many minimum coins would it take to form this total.

[hashirahmad]

A little heads up would be better. I have seen in almost all your videos, you just magically come up with some formula and start doing stuff from the word go. I am not saying that it doesn't make one understand the problem. But, framing the problem or at least some info on what the algorithm is doing and why it is doing it will be much better.

[reehji]

dude, i've been spending 2 days to understand dynamic programming. However you sir, explained the data structure aspect of it best. The concepts are simple, but using the right data structure and logic to store the solution isn't always so clear :)

[MrMalish]

I assume you can change:
for (int i=1; i<=total; i++)
to
for (int i=coins[j]; i<=total; i++)
and delete if(i>=coins[j])

[derrsonn]

This is the best I've seen that gives the optimal solution instead of all of the combinations. Nice.

[adityaakshay]

people wondering with the formula.. the general rule is that every time u traverse a number keep in mind that that number will carry ahead in this case {7, 2, 3, 6} means Iteration 1 : 7, Iteration 2: {7, 2}. He doesn't draw that so looks confusing. Also just sort the array to {2, 3, 6, 7} and then its just knapsack formula min(X[i-1], X[i-nums[j]]+1). no need to traverse in j u can traverse in i. This logic is applicable for subset-sum, partition sum, knapsack, coin change, box stacking.

[itspush]

googled a lot for such kind of explanatory tutorial only to find out this one is very helpful among all.

[sarahharber]

Best video I've seen and I looked for hours. Thank you for being amazing!

[chandrashekhar]

Very Nice and Crystal Clear Explanation..

[SiddhantEkale]

You're the best :)! We follow your videos when we solve problems!

[michaelz]

Tushar -

THANK YOU. Your explanations are so clear, and you doing examples on the whiteboards makes it so easy to understand. Don't listen to the comments that say you are bad at explaining things. You're doing an amazing job :)

- Michael

[rahulthankachan]

Hey Tushar! This is great :) You have lot of patience !

[vicentefelipe]

instead of having that if(i >= coins[j]), just have the second for loop start at coins[j]

[sagardafle]

Thank you so much, Tushar for taking up the efforts to solve such tricky questions with clear examples and running it.
Very much appreciated sir :)

[KanagaveluSugumar]

Tushar, No one can beat you on teaching us algorithms :).

[RahulKumar-jlkz]

from where did you get that formula? Suppose if i am dealing with a new problem how will i know the subproblem and get the desired formula. In algorithm it becomes important for us to know the reason behind to use any particular formula.

[shashwatdev]

here you cant write 0-total amount (289) how to solve this ?
Given a value N, if we want to make change for N cents, and we have infinite supply of each of S = { S1, S2,
.., Sm} valued coins. Make a change for an amount of 289 Cents using the smallest possible number of
coins. Consider the available coins are:
• dollars (100 cents)
• quarters (25 cents)
• dimes (10 cents)
• nickels (5 cents)
• pennies (1 cent)

[hamdyahmed]

Thank you Tushar.
Let me tell you that you are the best one I understand algorithm and solutions to problem from (Y) .
And let me tell you 2 additional things here:
1. You need to explain how the formula used here is made.
2. you always need to include the implementation code in the video and walkthrough it, as you did in this video.

[hurlok]

Great comprehensive explanation, thanks!

[FR]

Can someone explain why in theory the greedy method of choosing/not choosing a coin at each recursive step wouldn't work? I understand that it doesn't work if you're given coins that don't add up to the amount, but how would you know that from just reading the problem?

[benOutlier]

Hi, just wondering can you pointing me to chapter and section, best the the page number of CLRS, where the proof of which denomination works for the greedy algorithm can be found?