Change Making Problem - Dynamic Programming

Something that bothers me about every single video and book about computer science, is the tendency to use very short and difficult to interpret variable names. It would have been much easier if for example c[p] was named numCoins[targetSum] or something along those lines. Some of these single-letter names always end up being completely arbitrary and the best you can do is try to remember what they mean when the slide is changed (or you flip the page in your book).

[@partyhatman]

I agree 100%. Naming conventions can make this soooo much easier to understand and learn.

[@SinCityGT3]

Agreed. Even when they explain the mathematics it's hard to follow... S` = S {Dk}... what?

[@irvinge4641]

one thing that confused me is in the beginning he introduced S as optimal solution and S', but later on he used c[p]

[@kar2k]

YES!!!

[@revathik9225]

I read several tutorials and watched several videos but this is the only video from which I could understand coin change solution using DP. You're the best.

[@AhmedToulan]

Saying the numbers without showing the equations you're using can be pretty confusing. Otherwise, great video.

[@dryoldcrabman6890]

This is the first explanation of over actually understand. You rock man! Thanks you.

[@nfanni97]

Thank you so much, this helped me write the code in less than an hour (while understanding what I was doing). Exactly what I was looking for, a clear, simple explanation without he actual code so i have to do something myself :D

[@anumali5907]

Great work!!!Loved the explanation and the demonstration :D

[@samiulhoque3769]

Thanks alot foe the great video ^_^ Please add the equation in the video for each iteration, it is kind of confusing without it.

[@irvinge4641]

Also when you say "last coin" used in the s[p] array, its the di that corresponds to the minimum chosen in c[p] right?

[@mysteriousbillionaire7349]

at p= 10 cents how is the choice made between 6 coins and 2 coins, are both the function run and compared?

[@skinpa]

Shorting before 3:17 you say that replacing S' with X would contradict S being optimal. Can you elaborate on that?

[@opiumgrowing682]

Suppose by way of contradiction that S' is not optimal and that the optimal solution is X (X uses less coins to make n-d_k cents). Then we could add d_k cents to X (say Y = X+{d_k}) and Y uses less coins to make n cents. But Y can't use less coins than S from the assumption that S is optimal. That is the contradiction.

[@jebediah2345]

Thank you very much, this was very helpful.

[@xMrJanuaryx]

Are you suggesting we use recursion? For instance you say c[p] = (0, if p = 0 or min(c[p-di]+1) if p > 0). So is min some undefined method that your referring to? Is this a typical form of describing a recursive solution to a problem that you might find in a textbook or something? I do not think that I understand the vernacular. Also confused because sometimes di seems to be a position in an array and other times di seems to be an actual coin value??

[@DeaconOfTheDank]

Great explanation. Dynamic programming problems are always a little tricky for me so your video goes a long way for me. Keep 'em coming!

[@johnhammer8668]

all other videos on KZbin start from drawing the tables without proving the optimal substructure. thanks so much for the format (first proof then recurrence , then explanation) this is exactly how intuition is taught.

[@KanagaveluSugumar]

Thank you! so much for explanation of why greedy algorithm fails here. :)

[@arianphilips5777]

new suscriber

[@duaa9649]

That was super helpful!

[@osrax]

excellent video!

[@usamakhalid1990]

Whats di?

[@mysteriousbillionaire7349]

highest available coin that is >= to P

[@irvinge4641]

subscribed bruh

[@trackbit9hopugneru660]

A nickle is at least 5 € Cents now in the Netherlands it will be for sum reason..

[@irvinge4641]

this would be considered a bottom up implementation right?

[@irvinge4641]

c[p] is the same as optimal number of coins right?

[@arianphilips5777]

magnificent explanation

[@ONeillCode]

Nice explanation!

[@vishwanathbhat1382]

Very confusing :|

[@michaelliu825]

Awesome explanation!!!!