11
Sep

Algorithms: Solve ‘Coin Change’ Using Memoization and DP


Hi, I’m Gayle Laakmann McDowell, author of Cracking the Coding Interview. Today I want to talk about the make change problem. So we want
to give someone a certain amount of money and we have a list of all the
denominations. And the question is how many different ways can we do that? So
let’s walk through this for a particular possibility. Suppose we want to make 27 cents out of
these coins here. Well the first thing we need to figure
out is, well how many quarters are we gonna give? Are we gonna give one quarter?
Are we going to give zero quarters? We can’t give any more than that. Once we’ve decided how many quarters to
give out, our problems actually been reduced. Once, if we give out 0 quarters
then now we’re just trying to make out, make 27 cents from just dimes, nickels
and pennies. If we give out one quarter then we’re trying to just make 2 cents
from the remaining options which obviously there aren’t a whole lot of ways
of doing that. Now we just repeat this process. So how many ways are there of
making change, of making 27 cents from dimes nickels and pennies? Well let’s go through the different
options. We could give zero dimes. Let’s start with dimes. It goes 0 dimes, 1 dime, or two
dimes, and same thing for this other one but the possibilities are much more
limited there. So if we keep going through this process we’ll eventually get
to the point where we have a definitive answer. So we’re saying how many ways are there
of making change from seventeen cents given just pennies? That’s one. If we’re saying how many ways
can we make change of seventeen cents from just a two-cent piece, so this is
with different denominations, that’s going to be 0. And those will be our base
cases. So let’s try a new example here with a bigger values and little bit more
denominations. So suppose we’re trying to make 79 cents from half dollars,
quarters, dimes, nickels, and pennies. So one option we’ll explore is making 79 cents with 0 half dollars and two quarters, and then the remaining 29 cents
from dimes, nickels, and pennies. Another option though that we’ll explore is
making 79 cents from one half dollar and 0 quarters and the remaining
29 cents from dimes, nickels, and pennies. So note that these two problems have now these two paths have reduced to the same sub problem although we got them in a different way. One uses fifty cents a 50-cent piece and
the other one uses two quarters, they have the same sub problems so we don’t
need to compute this twice. Once you’ve computed it once, just store it for future
problems. So that said let’s turn to the code now. Whenever I do a memoization
problem I like to start off with just a straightforward recursive approach. It helps
me wrap my head around the problem a little better. So this is a make change
function and it’s just going to be straight forward recursion. It’s going to return
along so that it can avoid integer overflow, and it’s going to take in the
denominations and the amount of money. Now, when we just talked through the problem
earlier, we had had this array basically popping off the first element. That can
get kind of inefficient to shift and shrink this array because that actually
requires creating a new array. So a better approach is to just pass in some
sort of index which tells us what coin we’re currently considering. So what we’re going to
do is take, you know, take the first coin or take whatever index is pointing to and
if it’s say 25 cents, consider saying what if we have one of those, or 0 of those, one
of those, two of those, etc. And I’m gonna come back and add the base cases
later. So what I’m gonna do is recurse on
each of these options. So this is going to be the amount of money we have used
from this particular coin. So while amount with coin is less than or equal to the amount of money,
then we’re going to say, ok, the amount of money remaining we need to make is coins
of index, oops, money, it’s money minus amount of coin. Then recurse on this so I’m
gonna need some long number of ways. Recurse on this and add
that and keep track of that sum as we go. Remaining index plus 1, so count how
many ways there are of making the remaining amount of money with the
remaining coins, and then increment amount of coin, by the value of that coin. We
could alternatively actually just have amount to go from 0 1 2 3 4 and then
multiply that by the size of the coin. Doesn’t really matter too much which
approach we take, and then return ways. Now my base cases here. Well if we’re out of money then so, perhaps you have zero cents left, then
well that how many ways are there making 0 cents, with doesn’t really matter what the coins
is. If we run out of coins, but not money then the options are 0. So if
index is greater than or equal to coins dot length, then return 0 so that’s
our recursion. It’s always nice to give the caller a little helper function just
to wrap that good, it makes a little bit easier, so they don’t have to worry about
what the parameters are. Ok now the memoization part. The idea here is that
whenever we start to try to recompute the same problem and we want to say, wait
we’ve already done this before, return the stored value. Question is, how
do we define whether or not we’ve seen the problem before? Sometimes people will use just money at,
will use some sort of hash map, right, that maps from the problem with it however we
represent it, to the answer to that problem. So sometimes people will use
money as the key in this hash table and that’s actually not sufficient. Just because we’re trying to compute the
number of ways of making change for 29 cents doesn’t mean the number, that the
coins being used there are the same. So we need a key that actually represents
both the money and the index. So we could use a class that wraps both of those but
even simpler is a simple string. So just use a simple string that’s basic
concatenation of money and index and then we’ll have a memo table that I’ll
use, that’ll be a hashmap, up string from a string to a long, and
I’ll call that memo and now I’ll say if memo dot contains key, of key, return memo dot
get of key, and then at the very end here, update my memo table, key comma ways and
when I call this function I’ll pass in that memo table. And then I also need to
pass it in down here. Ok so hopefully this will work. Alright so now one thing I want to point
out here that is a very common mistake for candidates to make is this key. So here I’ve
concatenated this string representation for the money and the
index, you want to make sure there’s a separator there because otherwise you
could have a situation where your concatenating like, you know, I’d say 29
plus 1 and that gets confused with 2 + 91. So just be careful for that. You want
to use a little separator there like a little dash will work fine, just get in that habit.
So this is a little bit trickier memoization problem but it’s
not overwhelmingly difficult once you get the hang of these problems, so I
really encourage you to practice memoization problems a ton. If you want
to as a follow-up have an extra challenging algorithm, you can flip this around and
try to tackle this iteratively. It’s a lot trickier but one tip is think
about the what is the very last thing that gets filled in on this memo
table. Then how can you backtrack and fill in each cell of the memo table based
on what work you’ve done before. So it’s a really good exercise that really tests
your understanding of this. But it’s not something that, at least in
this complexity, tends to be asked in interviews. But again really really
encourage you to practice memoization problems, they’re really really, they’re a lot
easier once you get the hang of them. Good luck.

Tags: , ,

23 Comments

  • GTAMysteryHunter says:

    Thank you for these. 🙂

  • kunal sharma says:

    int[] coins= {41,34,46,9,37,32,42,21,7,13,1,24,3,43,2,23,8,45,19,30,29,18,35,11};

    int money = 250;
    long ways = Solution.makeChange(coins, money);

    for this it is giving negative output
    15685693751

  • Piyush says:

    It would have been better if you could talk about the time and space complexity of the solution.

  • A55tech says:

    What is the Big O notation of the non-DP and DP solutions?

  • Rahul Sharma says:

    By far the best explanation!

  • AKSHAT SHARMA says:

    what is quarter at 0:42??

  • AKSHAT SHARMA says:

    i think your code do not consider the same index again , if not , how it will ??? explain

  • Sachin Kolachana says:

    Use quarters or either 25's to be consistent. You are basically making this more complicated.

  • Rajat Pawar says:

    Please do not assume that everyone using this lives in the United States of America. Please try to make your videos understandable to the global audience, because currently it is just gibberish with quarters, nickels, dimes and what not.

  • ONeillCode says:

    Great video!

  • Tomek says:

    The question on HackerRank states that coin is a value between 1 and 50. So basically it say's it can be 49 or 13. I hate when one time you supposed to make assumptions to real world and other time have tests failed and find out that "you should have been reading more carefully".

  • Hajra Naqvi says:

    Can anyone tell me about its recurrence relation ???

  • Jay Patel says:

    Did I just hear "make out" !? 0:37

  • Jayaram Prabhu Durairaj says:

    how many ways to make 0 money => 1 way ? hows that ?

  • Ultimate Sin says:

    How do you come up with elegant solutions like this off the top of your head? I understand why it works when stepping through it but… it looks like you begin with thinking about base-conditions for stopping the recursion loop and returning the smallest possible answer (you didn't here but you usually do).. it's just difficult to extrapolate and break-down how you come up with this solution because it seems like a chicken/egg scenario where the pieces all depend on eachother and you need to know them all at once.. hopefully it will come overtime and practice..

  • Chiranjib Ghorai says:

    I am a slow learner. Watching the video by ONeillCode – https://www.youtube.com/watch?v=jaNZ83Q3QGc before the Hackerrank one made it easier for me to get the grasp of the solution. And once you understand this and the Minimum Coin Change , you can solve a lot of other DP problems using similar tactics!

  • Miggy Reyes says:

    I am still confused as to why we need to store the money and index into a hashmap

  • Steven Smith says:

    Thanks so much for your video. It was really helpful!

  • Augustus Yuan says:

    For people international

    penny = 1
    nickel = 5
    dime = 10
    quarter = 25
    half dollar .= 50
    dollar = 100

  • Ersin Erdem says:

    Could you speak a bit slower please? In all those tutorial videos I have watched, this was the first time I opened the subtitles 🙂
    Thank you for the video by the way 🙂

  • I K says:

    I wish she didn't got through the solutions so quick and actually explained each line in detail…

  • Vj Ar says:

    Dumb question: number of ways to make change for zero cents is One. Why is that? If I had no money, then how can I make change for it. Just trying to understand the intuition here.

  • Aisha Kassim says:

    good video, change the font next time and perhaps introduce the coins to those that are international so we can better understand the video.

Leave a Reply

Your email address will not be published. Required fields are marked *