Coin Change Top down dynamic programming

Given a total and coins of certain denominations with infinite supply, how many minimum number of coins would it take to form this total.
/ tusharroy25
github.com/mis...
github.com/mis...

[@mukundsridhar4250]

Thanks Tushar for all your videos. You have enrichced the lives of so many people.

[@mojahidislam9717]

it's great that you r explaining the code too ....please keep doing that...your efforts is seriously helping many students like me.....

[@stephengardner5746]

This is the best explanation I've seen. Thanx

[@nemanjastankovic941]

great explination. i like the way you structure your lectures: problem definition->example->code. best regards from serbia

[@khumoyunakhmedov4562]

thanks very much brother. You threw a shiny light on my understanding of this problem

[@samuelmoon3739]

Clear and concise explanation. Thank you

[@debiduttamishra4760]

As always.. Brilliant explanation Tushar.

[@swagatikachoudhury2115]

Same solution but little change: public static int coinChange(int[]coins,int sum, HashMap map) { if(sum==0) return 0; if(map.get(sum)!=null) return map.get(sum); int min=Integer.MAX_VALUE; for(int i=0;isum) continue; int num=coinChange(coins,sum-coins[i],map); if(num

[@PiggyGirlBeauty]

Thanks for your vids!

[@AmritpalSingh-gm1eu]

Hi Tushar, First of all, Great Explanation of the top down approach. However, I wanted to make one point regarding the Time complexity of this algorithm. As per the explanation, it is M X N, where M is the total that we are trying to achieve (5 in this example) and N is the number of coins (3, in this case). So M X N is achieved as we get down to 5 levels of recursion and in each recursive iteration, we have a for loop of 3 iterations, hence 5 X 3. However, in this example, the smallest denomination of coins is 1 and hence each recursive call is stepped down by reducing 1 (equivalent to the total - coins[i]), so it takes 5 recursive iterations. In case the smallest denomination of coin is not 1 and a bigger number, say 2 or 4, the time complexity is further reduced to (M/smallest coin X N). Please let me know if this makes sense.

[@AmritpalSingh-gm1eu]

Also, After going through the video explanation and the code at the end, it seems they are out of sync. In the explanation, it seems that we are first calling the recursion and after the recursion returns we loop through each coin for that specific balance. However, in the code, the recursion is being called inside the loop, thus generating the sub trees for each coin. My understanding can be wrong, but I created my quick and dirty version according to the explanation. I would appreciate if you could comment on this. rextester.com/SLUGL76503

[@iamdipankarj]

Please make a Top down approach for the knapsack problem.

[@AMAR18MEHTA]

Hi, which video have you discussed bottom-up approach for the same problem, the one mentioned at 0:14?

[@SamVillage]

Bottom-up dynamic programming kzbin.info/www/bejne/j2G9on6midSHn8U

[@moamenahmed7543]

What to do if I want to print the values which form the minimum no. of coins ? (With Top Down Approach)

[@slmnkh]

great video! thanks!

[@kartikayy]

Always prefered watching your tutorial videos... A very nice explaination Indeed When Trie tutorial will be coming??

[@kartikayy]

Dictionary thing . and How it is implemented

[@jlecampana]

Are all dynamic programming problems as difficult as this one?

[@komalsoni1722]

lol this isn't difficult at all

[@Amanyadav-ec3hn]

Thanks a lot!!!

[@kobe2453]

can you reduce the sound from keyboard

[@theOceanMoon]

Great explanation but bottom up much simpler

[@tonyjiang4991]

He has a bottom up solution in another vedio.

[@1clutchx675]

why 14 disliked i mean dislikers are blind or def or may be have some mental problems may be they hold there device upside down.