# Dynamic Programming lecture #2 – Coin change, double counting

Hi, I’m Errichto. Welcome to the second lecture

on dynamic programming. Today I will show you how to solve 3 quite

similar problems and we will talk about the main difference between problems where we

optimize some value and we count ways to do something. And that difference is double counting, an

issue that makes counting problems much harder. The first problem is Combination Sum. We are given the target value N and some allowed

numbers, we are asked to count ways to write N as the sum of those numbers with allowed

repetitions and the order also matters. For example, if the target value is 4 and

the allowed numbers are 1 2 & 3. Some possibility is [1+1+2], which is equal

to 4, but also some other possibilities [1+2+1] which is also 4. All the ways here are written on the left

and there are 7 of them. So the answer is 7. Like I told you in the previous lecture, it’s

good to think about DP as what is important so far? In previous problems, it was what we need

to know when we are at some position what we need to remember about previous choices,

may be the number of jumps. Here, after we already write some part of the sum, let’s say 1 & 2, it isn’t important how many

numbers there are. Because we don’t care about it in any way,

we care about the sum. Here we know the sum is 3 and this suggests

that this should be dimension of DP, the state. Since we are counting the number of ways to

write N as something, then DP will be int dp[some dimension(state)]

and that int denotes the number of weights. dp[i] will be the number of ways that we are

at state i and i denotes the sum, i is the sum so far. Then we can in some way initialize that, I

will say dp[0] is 1. And then what transitions we can make, if

we have some equal to 10 and the allowed numbers are 1 2 & 3, then I can get sum 11, 12 or 13. Let’s see some implementation of that. The first code is quite standard we initialize

dp[0] as 1 there is one way to get the sum 0. This is just empty sum and then we compute

every next dp[i]. If we want to get the sum i then we iterate

over the last number x, we can even simulate that with our example. dp[0] is initially 1 then every next one is

0 up to dp[4] and every next one is computed as the sum of 3 previous values quite similarly

to Fibonacci numbers where this will be 1 this will be the sum of dp[i-1] and dp[i-2]

which is 2. This one will be 4, the sum of previous three

numbers and this one will be 7. The second approach is a bit different. It’s so-called forward or push dynamic programming

where we already know value dp[i] and we use it to update future values. We again start from our array [1 0 0 0 0]

then we start from i=0 this time, we use 1 to increase future values. We know that there is some number of ways

to get the sum=i, we consider next element to add to update future values. For this one will update this 0 to 1, 0 to

1, 0 to 1 next 3 values because in our example nums are 1 2 & 3. Then we are at this i, the value is again

1, we update next 3 values 2 2 & 1. Then we are at i=2, we increase future values

and finally, here we increase dp[N] by this value 7. Computed values are the same, it’s just that

the method is different. In the next lecture, we’ll see more examples

of this forward DP. The next problem “Coin change” is quite similar. We’re given denominations of coins and the

target amount N. What is the minimum possible number of coins

used? The main difference is we previously had to

count ways, and here we’re finding the miminum possible number of coins. For N=11 and coins [1,2,5], I can get 5+5+1. This way I get the sum 11 and I use three

coins, so the answer is 3. It’s impossible to use fewer coins. The next one I can use 3+3 which gives me

the answer 2. Again, you can think about the greedy approach

because this is optimization problem. If you every time take the biggest possible

coin… for N=6 maybe you would want to take 4 first,

then the remaining value is 2, you need to make 1+1. This is not optimal. This means the greedy doesn’t work here. The code will be very similar, the solution

will be very similar to the previous one. It’s just that dp[i], instead of being the

number of ways to get this sum, it is the minimum possible number of coins. Let’s see the comparison of two implementations. I took the first code and slightly modified

it. The initialization is different. I can’t leave everything to be zero because

then I will think that DP of n is 0 that 0 coins are enough to get the sum of N. But if we know to compute dp[i], I iterate

over the last coin and I find the minimum over dp[i-(that last coin)]+1, i-x is the

sum so far before that last coin plus 1 because I’m using one more coin. I could also put that plus 1 outside the bracket,

I mean I could find the minimum over dp[i-x] and only then add a one, but it doesn’t matter. Well in this code and the previous one what

you should be careful for is of course amount of boundaries error. This is pseudocode but in actual implementation,

you need to check whether i-x isn’t negative, plus here, we initialize all the values to

infinity and the sum equal to 0, you can get with 0 coins. This problem is certainly the hardest in this

lecture. It’s again Coin change but this time we were

counting the number of ways. We are given the denominations and the target

amount and what is the number of ways to make up that amount? This time though we say the order of numbers

doesn’t matter but what matters is multiset of coins. If you are in a shop and you want to trust

a bunch of coins to pay exactly n then the order of them doesn’t matter we don’t give

those coins one by one. And this is the difference from two problems

ago from Combination sum where we’re we were writing N as the sum of numbers and [1 1 2]

was counted separately from [1 2 1]. Here for target value 5 and coins 1 2 5 there

are four ways that I wrote on the left. If we would count every order separately then

instead of just [2 2 1], I would also count so [2 2 1] then also [2 1 2] [1 2 2]. And similar thing for [2 1 1 1] there would

be four ways. Here I have 3,4,1 & 1 the total would be 9

but this is a different problem the order doesn’t matter and the answer is 4. If we just applied the same dynamic programming

that for some already chosen elements remembers the sum, here sum=3, we would get the issue

of double counting or overcounting. You would separately count way with [2 2 1]

[2 1 2] and [1 2 2] because all of them give us the sum N in position dp[N]. We need to change something and now not only

the sum matters, we cannot say dp[i] is the number of ways to get sum i and that’s it

because we don’t want to double count any state, any solution. And not to count those three separately, I

will say that I want to only allow one of them. What makes sense is to count the lexicographically

sorted way, this is a unique representation of all of those. I want to not allow those two. Then in our already chosen elements, not only

the sum matters but also the last element and the next element cannot be smaller than

that. This time we’ll say that dp[sum][k], let’s

instead of k use last=>dp[s][last]. This is the number of ways to get the sum

of s where this is the last used coin. If we number coins from 0 to K-1, where K

is the number of them, then the memory complexity of our DP this time is O(N.K), s is up to

N and last is up to K-1 and every state with some sum and last, (sum, last). We should iterate over the last coin taken

maybe, we’ll think about that in a moment. But the trivial approach here would lead to

time complexity N.K^2 if you want to iterate over the last coin. But it won’t be necessary and we will get

N times K. If the state is sum so far and the last coin

then let say last coin had index 2 the next coin can be coin 2, coin 3,4 and so on. If we choose the next coin to be 2 again then

the new sum is 17 + nums[2], the last coin is still 2 then 3 and so on. From each of N times K states, we consider

K transitions this is why the complexity is N.K^2

Then at the end, we’ll say the answer is the sum over dp[N][?], the target value and the

last coin can be just anything, the sum over all those question marks. How to make the time complexity N times K? It’s very simple. It’s enough to say that from state (17,2)

you can get to state (17,3) you can imagine that last coin is 3 and from that state, you

will consider cases, where the next coin to take, is 3 or 4 or whatever else. Then you remove all those transitions and

you have only two. Actually, this changes the definition of last

coin a little bit. This is not the last coin but kind of the

limit for the coins that you used or you can use. If you used coins 0 1 1 & 2 you can say that

the last coin is 4 if you aren’t going to take smaller coins. If you write it this way and from (17,3) we

can get to either (17,4) or (17+nums[3],3) what represents taking coin 3 now, 3 which

is the last coin then we are fine every possibility like taking for example coins 0 1 1 2 4 4

and so on, every possibility like that will be counted and what is important is it will

be counted exactly once. When after taking 0 1 1 2 we are in this state

then we don’t need to iterate over all those coins that we take next. It’s enough to go to state that thinks the

last coin so far was 3 because we don’t want any more coins of index 2 then we’ll go to

(17,4) and from that we’ll get to that (17 + nums[4],4) which represents taking coin

4 and this doesn’t double count anything. Because in that graph of transitions, there

is only one path that corresponds to this so this multiset of coins. It must go like this if from (17,2) we go

with the other transition to this state that would represent taking another 2 when we have

already 0 1 1 & 2. And then either the next coin is 2, in that

case, we go to that state where we still can take 2’s, otherwise if it’s 2, if it’s 3 plus

then we go to the next state below 17 and 3. In the graph of transitions, there should

be exactly one path and then there is no overcounting. One more thing for this problem is that you

can get memory O(N) like for those instead of having dimension K you go kind after coin

and for every next coin from 0 to K-1, you update dp[i] then dp[i] would be the number

of ways to get this sum with coins considered so far. Actually, this is very similar to Knapsack

and we’ll talk about it in one of the future lectures. But yeah the memory can often be optimized

by one dimension. What we described so far has both time and

memory complexity O(N.K) The number of states is N times K and we have

just two transitions. You might notice that we actually did that

Forward DP or Push DP it’s also possible with Pull or Standard take from previous values

DP where dp[i][last] is computed from previous state then DP to that (17,2) you need to go

from (17 – nums[2],2) or from (17,1), it’s the same thing. There are just two ways to implement that

if you want try this problem or one of previous two, there will be links in the description

or in the pinned comment the first comment below the video. So you can try to implement this yourself. I mentioned already that the second value

of the state that last coin isn’t really the last coin it is our limit and there is a concise

way to now define the state of DP. dp[s][k] is the number of ways to get the

sum of coins already used equal to s where we used only first k denominations from that

array nums, we were allowed to use the only use first k values and then there are indeed

just two transitions from every state. From this lecture, you should remember that

in dynamic programming problems you must think what is important so far after we made some

decisions after we already chose some numbers, or in graphs after we got to this vertex. In easy cases it was just the sum of numbers

of already chosen coins, in harder one, it was also that last element and the other thing

is to think whether your solution will not double count some state like [1 2 2] and [2

1 2]. Those shouldn’t be counted separately but

our first version did count them separately and the answer would be bigger. Optimization problems are easier this way

if we want to minimize the number of coins used or maximize or something like that. It doesn’t hurt you that in that graph of

transitions between states there were two paths leading to the final solution to the

state. Because those will be counted twice in the

program that counts the number of ways if we just minimize something it doesn’t matter,

min(5, 5) is still 5, but 1 + 1 is not 1. So be careful about that, and that’s it. See you in next dynamic programming lecture. Bye. Bye.

Combination sum – https://leetcode.com/problems/combination-sum-iv/

Coin change (min) – https://leetcode.com/problems/coin-change/

Coin change (count) – https://leetcode.com/problems/coin-change-2/

Thank you so much!!! keep making these type of videos

Great video! After these DP videos, do videos on graphs please.

bro make a data structures and algorithms course which covers all the important ds and algo required for competitive programming

Hey Errichto,

Can u help me in understanding this problem and solving problems related with this similar concept?

Problem Link – https://www.codechef.com/problems/XORSUB

It would be a great help!!

And yeah great video…

Thanks.

Please explain DP using recursion.

in your first episode of dp :in staircase problem , how you got the intuition that you have to generalize it for i , then how you got the thinking that you have to solve it from i to backward rather than generalizing it from 1st or 0th step to i ? It's a bit confusing for a beginner like me how the thinking pattern deviates from problem to problem .

Great video again, thanks a lot

Really thankful for these wonderful lectures. Btw what would be the rating for the coin change problem or similar problems in CF? And if it were to appear in a DIV 2 contest, will it be A B or C?

Finally some great DP Series going one <3

Can u suggest some resources for combinatoric with dp,

your videos are so much helpful. please keep up the lectures on DP. liked it very much. Thanks a lot

Greate! Make a full series of covering different aspects of dp

I 1st like your video then see it.

wouldn't there be three transitions, say suppose we are at index i.

1 > we can pick it and remain at the same index.

2 > we can pick it and goes to next index i+1.

3 > we will not pick it and go to next index i+1.

I think you gave 1st and 3rd one. what about 2nd.

Thanks much!! Please do complete all possible questions that you feel would be good in dp and all tricks that would help us in CP down the line!! Great job!! Thanks again @Errichto.

Thanks for video lectures

Errichto, I think you should add a keyword in Video title hinting towards Iterative DP. If someone googles for Iterative DP, your Video has no keywords which will make it any relevant, someone might think it's just yet another recursive DP lecture.

Think "What is important so far"

First like the video because we know that the video will be good

Good video. I would suggest you to take hard dp problems for your next lecture (for eg:- https://leetcode.com/problems/maximal-rectangle/ ) etc.

Hey errichto i am cs student in india inspired by your great approach to problem solving!! looking forward to more in depth video on dp topics !!

You simplify the things so easy. Thank u

eagerly waiting for 3rd lecture on dp. errichto u r the best.

Thanks a lot. Keep up the good work. Take love

I don't get why dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

What if we want the number of ways to make up the amount 8 why would dp[8]=dp[7] +dp[6] + dp[5]

Many many thanks for dp series. Hope you will extend this series.

Thank you for all these videos plz make videos on combinatorics,number theory,game theory , geometry etc as these topics aren't covered anywhere

I didn't understand any shit

When the next part will be published? π

This video is great !

Really good video!! Can you please make some video of dp bitmask

make video on segment trees

Hey can you make videos concerning bit manipulation questions similar to the ones on leetcode I am having a hard time understanding the intuition to most of these problems.

thank you erichto..for such a wonderful knowledge sharing..which is very very useful for the beginners like me…soon I will learn the maximum things possible and use it for the betterment of the world…keep doing your good work…many people are eager to learn from some of the great people like you…I wish to meet you at least once in my lifetime…just to congrats you…I am from india…if you had a chance to come across Chennai,(a place in south India) just inform me through my number(9629906744)..so that I can meet you

really appreciate the tutorial! It would be really great if you could explain how this problem could be solved in any of the future dp videos, it seems hard and there's no proper tutorial for it. https://atcoder.jp/contests/abc134/tasks/abc134_f

Errichto we need the next lecture, please!

Really good video. BTW, how come most of your video views are ended with 100ish. Interesting

Hi Errichto,

I was doing machine learning for like 1.5 years and trying to get good at it. One day one of my friends challenge me on the Atcoder Educational DP problems. When I was solving the 3rd question, I couldn't come up with a solution. I started seeing your content. Then I started to explore you. I also came to know about the tourist. By looking at the level of content in your channel I often wonder how could someone stream this level of content free. Then I assumed that you must be showing a demo piece of your premium course here at youtube. But No. you are doing it free. All of them are free. Being a newbie to competitive programming, here is what I think you should do:

1. Everybody is telling to solve problems. But, which problem?

2. You are doing great. But just put 1 video for each topic e.g Segment tree, game theory, Dp. Then after that put a 10-20 beginner level problem's links in the description. Give 2-5 days to solve them. Then release the solution for the problems. After all, topics are covered, you can make all the problem videos as you have been doing on this channel.

Whenever a kid will start learning competitive programming, Every blog post, as well as content creator, will refer him to start from your channel. Like everyone suggests Andrew Ng's course on machine learning for a newbie in machine learning.

Today, I saw you on Joma's channel. It's good to see both of my favs in one place.

Love from India

East coast area

Avoid the double counting.

Avoid the double counting.

saw you on JOMA had to subscribe and hit the bell icon!

Here's my solution. Do you have any comments? I used recursion + caching, rather than your array-lookups.The 'solve' methods get the 3 answers you discussed.

class CoinSolver():

def __init__(self, coins, target):

self.coins = tuple(sorted(coins,reverse=True))

self.target = target

def _num_ways(self, target):

if self.val_cache.get(target):

return self.val_cache.get(target)

if target == 0:

total =1

elif target < 0:

total = 0

else:

total = 0

for c in self.coins:

total += self._num_ways(target -c)

self.val_cache[target] = total

return total

def _num_ways_distinct(self, coins, target):

if self.val_cache.get((coins,target)):

return self.val_cache.get((coins,target))

if target == 0:

total =1

elif target < 0:

total = 0

else:

total = 0

for i, c in enumerate(coins):

total += self._num_ways_distinct(tuple(coins[i:]),target -c)

self.val_cache[(coins,target)] = total

return total

def _min_coins(self, target):

if self.val_cache.get(target):

return self.val_cache.get(target)

elif target in self.coins:

min_val = 1

else:

min_val = target

for coin in self.coins:

if coin < target:

cand_val = 1 + self._min_coins(target-coin)

min_val = min(min_val,cand_val)

self.val_cache[target] = min_val

return min_val

def solve_num_ways(self):

self.val_cache = {}

return self._num_ways(self.target)

def solve_num_distinct_ways(self):

self.val_cache = {}

return self._num_ways_distinct(self.coins, self.target)

def solve_min_coins(self):

self.val_cache = {}

return self._min_coins(self.target)

Hey, I love your video, too bad you dont post out more content, you got a great and systematic way of talking with a foreign accent that makes it easy to remember. Also why do you have 2 separate channels? Is it not a waste? I think people would appreciate subbing to one channel to have all videos in one place.

Thanks you to provide this information

Joma Gave this channel a blow.. and I hope Erri will give some interesting content on it, help many aspiring coders…

http://lightoj.com/volume_showproblem.php?problem=1005

Errichto can you explain this problem how to solve it with dp?

Love your videos. When will you make the third video on DP, Looking forward to it.

could you make a video about this problem? https://codeforces.com/problemset/problem/1188/C

thank you

Great video Errichto! Would love to see the famous egg drop problem.

best video ever for learning DP! thanks bro!

love the content, please make videos on backtracking!

We can also use the nested for loop in a different fashion to avoid the repetition in 3rd problem :

dp[0] = 1;

for(int coin : coins){

for(int i = coin; i<=amount; i++){

dp[i] += dp[i-coin];

}

}

return dp[amount];

Hi errichto, what exactly do we return when i-x falls out of bounds , below 0?

You are literally like a god for me right now

Why the fuck does he have so less subscribers…..ohh…god….. people want to see Kardashians eggs but not this gold…….God save this world…btw I subscribed π

How do you come up with relationship?

for 1…N

for x in nums

dp[i] = dp[i-x]

Nice presentation

Hi Errichto,

Can you please explain again the part where you changed time complexity from O(n.k^2) to O(n.k).I didn't understand(Around 12:20 in the video) it properly.

Thanks in advance.

Also ,please suggest where to practice dp problems to master it.

how to find the pattern to get the state and recurrsion? Can you please elaborate it?

What does it means this transition: (17,2) => (17+nums[2],2) 11:35

17 is the sum need to get by set of cions.

2 is a last coin in an ordered set. – this is clear.

But (17+nums[2],2) – this transition is totally unclear, why do the sum changes?

UPD: Its clear now (sum: 17, last_coin_index: 2).

than you

Thanks Errichto !!!!!!πππ

Thank you genius ! π