# 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.

Thank you for these. ðŸ™‚

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

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

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

By far the best explanation!

what is quarter at 0:42??

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

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

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.

Great video!

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".

Can anyone tell me about its recurrence relation ???

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

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

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..

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!

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

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

For people international

penny = 1

nickel = 5

dime = 10

quarter = 25

half dollar .= 50

dollar = 100

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 wish she didn't got through the solutions so quick and actually explained each line in detail…

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.

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