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

[zFGiveNLATAM]

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

[martinjoseph]

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

[mikefalchek]

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.

[shatadruroy]

Finally, I can start dynamic programming peacefully again!!

[StackJobs]

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

[Raghav]

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

[hendrikmartina]

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

[princem]

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

[tusharroy]

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

[hamidmirza]

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

[nicksteiner]

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

[inversemetric]

Thank you for your work demystifying this tricky topic!

[binayakthakur]

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

[acidroot]

Best videos about DP! Great! 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.

[DC-dndi]

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!

[vedaanish]

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

[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 <= n; i++) {
if (i - coin >= 0)
dp[i] += dp[i - coin];
}
}
return dp[n];
} This gives combinations instead of Permutations (where order matters)

[DavidCastro-sniy]

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

[shatadruroy]

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