12. Coin Change. Part 1. (Dynamic Programming for Beginners)

[@andreygrehov]

Next video: kzbin.info/www/bejne/nJWzlJlpopx4ntk Previous video: kzbin.info/www/bejne/lZrCn4eZrN6bY6c

[@zFGiveNLATAM]

This is fantastic I spent all day looking for a video that explains how to solve this problem using dp. Thank you !

[@shatadruroy3926]

Finally, I can start dynamic programming peacefully again!!

[@mikefalchek1868]

Just got to this video a few years after you posted it - this series is helping me so much. Hope your family is doing the best they can be, and let us know if there's any way we can help.

[@StackJobs]

And coin change is another combination problem. Much thanks Andrey!

[@martinjoseph1398]

Thanks Andrey! Very clear explanation 8:41 was my AHA moment

[@hamidmirza333]

I am new to DP and your DP series is really helpful for me.

[@anniehu4929]

The new intro is so cool!

[@hendrikmartina3552]

My body is ready!!! Nice to see you back!!

[@Raghav1205]

Glad you're back. Can you consider doing the document distance problem next. Thanks :)

[@praveenkumarsadhasivam]

I think, drawing the recursion tree first and then deriving the F(n) based on the recursion tree helps in easier understanding of this problem.

[@inversemetric]

Thank you for your work demystifying this tricky topic!

[@nicksteiner9902]

Going through this from the beginning to end and the song in the beginning killed me!

[@tusharroy6182]

Glad You are back! Hoping Fabulous content as usual.😁

[@shatadruroy3926]

Andrey if possible, please in your later videos solve more matrix based questions like Leetcode Cherry Pickup II, Leetcode Dungeon game. I somehow find it really hard to figure out the requirements of these problems and place them in the approach which you use to solve dynamic programming

[@binayakthakur5122]

completed last 10 videos in last night :) best videos on dp on net

[@andreygrehov]

Thank you, Binayak!

[@anniehu4929]

Same! I have been working through all of these videos this week so I can prepare for my interview with Google on Friday. These are the best resources I've found so far to learn DP as a beginner and it is so clearly explained and Andrey is really a good teacher :)

[@acidroot7126]

Best videos about DP! Great! Thanks! :)

[@phanisusarla]

Thanks Andrey!

[@tecHSonic]

Finally you're back

[@vedaanish2015]

Thanks, nice explanation. but small confusion about base case F(0) some times it is 0 some times 1

[@andreygrehov]

That comes with practice. When you are counting (a problem is combinatorial) things, doing nothing usually counts as 1. When you are minimizing things (an optimization problem), f(0) is usually 0.

[@vedaanish2015]

@@andreygrehov Thanks a lot

[@codeduel]

If order does not matter, Here is the correct version: public static int makeChange(int n, int[] coins) { int[] dp = new int[n + 1]; dp[0] = 1; for (int coin : coins) { for (int i = 1; i = 0) dp[i] += dp[i - coin]; } } return dp[n]; } This gives combinations instead of Permutations (where order matters)

[@DC-dn2di]

Hey thanks for providing this lecture. I'm learning DP and finding the topic confusing. When you move to F(3), why are you taking 1 and returning 2? Where does the 2 come from? Wondering why you don't take 1,1,1 Thanks in advance!

[@glennpavel4800]

Thanks for sharing Andrey, I still don't have clear why f(0)= 1 , I learned a lot with your series

[@andreygrehov]

In minimization problems, f(0) is usually 0. In combinatorial problems (when you need to count things), f(0) is usually 1.

[@andreygrehov]

Essentially, you just need an induction base, the base case. A base case can be a solution to at least one subproblem. Solve the simplest subproblem first, call it your base case, and then use it as a starting point for all the other subproblems.

[@glennpavel4800]

@@andreygrehov thanks Andrey is exactly what i needed! great job!!!

[@dima86d]

As far the talk is about sets (of coins), you could consider the 0 case as an empty one. There is only one such set.

[@DavidCastro-sn3iy]

Glad you're back!, since the last time post i've been waiting for a new video hehehe. I want to speed up my dynamic programming prep, any material you recommend other than your videos (which are amazing) ?... thanks in advance

[@andreygrehov]

Thanks a lot, David! Hm...good question. I would recommend Introduction to Algorithms by Cormen. I think this book is amazing. Once you read a few chapters, try to solve as many problems as possible. When it comes to DP, practice is a must. Start with Easy problems first. Solve each problem in a few different ways-an important step, which will prep you for Medium problems. If you can't solve a problem, don't be discouraged-open a solution and then try to solve that same problem in a different way. This "different way" moment is essential, so make sure not to ignore it. Good luck!

[@DavidCastro-sn3iy]

@@andreygrehov thank so much! i'm doing several problems, at the moment your framework has been such a nice tool to solve them in better way. Keep up the good work man! Greetings!

[@princem8779]

on 7:18 where is F(2) + F(0) coming from. Please clarify that. isnt it F(1) + F(2) from the line above

[@defe665]

You can't go to F(1) from F(3) in one coin. The line above means you either give 1 with remainder of F(2) or giving 3 with remainder F(0)

[@НикитаПрилепин-д7д]

Мне кажется, что задача решена не совсем корректно: рассмотрим ситуацию coins = [1,5], n = 6; Если проходиться сначала по i от 1 до 6 мы получим, что dp[6] = dp[5] + dp[1] = 2 + 1 = 3, т.к. посчитали 1x5 + 1 и 6x1. Правильнее сначала проходиться по массиву из номиналов, а затем уже от 1 до n.

[@spinacker16]

Best explanation ever! TY

[@10011100010]

Welcome back!

[@andreygrehov]

Yay! Thank you!

[@muhamadaminibragimov5096]

Thank you very much

[@nivethagovindan9741]

Wow!! Was waiting for this... :)

[@andreygrehov]

Thank you, @Nivetha.

[@jayarohith3883]

Good representation

[@sjha2048]

Missed you!!

[@andreygrehov]

Thanks, Sahil! I missed you too, guys. Back to work 💪🙂

[@alex_aleluia]

thank you so much

[@glensee7506]

I love it, thanks!

[@shrek1412]

class Solution { public: int change(int amount, vector& coins) { vector dp(amount+1, 0); dp[0] = 1; for(int i=1; i= 0){ dp[i] += dp[i-coin]; } } } return dp[amount]; } }; I use the same approach in C++ to solve leetcode 518 coin change II but it did not pass the test. Anyone knows why?

[@stuband4159]

Cannot understand your definition of the problem. Do you mean "given an unlimited amount of coins in various denominations how many ways are there of making an amount of size n?" What is all this I give 3 and he gives you back zero? It's very confusing and makes me think that is not the problem or is it? I agree the definition of the problem is key but I don't think you have successfully done that.

[@andreygrehov]

> Do you mean "given an unlimited amount of coins in various denominations how many ways are there of making an amount of size n?" Yes, that is correct. In the case of F(3), we say that if we return 1 cent, then we're left with 2 cents. If we return 3 cents, we are left with 0 cents. We have to consider the 0 cents case, because we use the same "pattern" sort of speaking, when we consider 1 cent (we're left with 2 cents). Every time you come up with a transition function, you can't deviate from a pattern that you use for each part of your formula. We say, if we return 1 cent, then we still have to return 2 cents.

[@stuband4159]

@@andreygrehov nope I don't follow. Given my definition of the problem which you agree with then, if I want to change 4 cents there are only two ways of doing this, 1 + 1 + 1 + 1 and 1 + 3 given only 1, 3, 5 and 10 cent coin denominations - but you claim there are three and your program also returns the answer three. What is the third way? Either I have not understood the stated problem (entirely possible) and we are at cross purposes or there is something wrong here. Which is it?

[@andreygrehov]

@@stuband4159 the reason why the answer is 3 is because 1 + 3 and 3 + 1 are treated as different answers. In lecture 15 we discuss how to treat 1 + 3 and 3 + 1 as the same answer.

[@stuband4159]

@@andreygrehov Ah right, so this is a permutation problem, the examples you gave on the whiteboard are ambiguous and I assumed a combination problem, therefore I think you should state that up front when you whiteboard it would save a lot of confusion - maybe you did but it was a hard to follow session.

[@pawankumarmeena6737]

So loong

[@andreygrehov]

Haha, yea! Sorry, man, haven't seen my family for several years. But I'm glad to be back! Thanks for being part of the DP journey.