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.

61 thoughts on “Dynamic Programming lecture #2 – Coin change, double counting

  • June 19, 2019 at 10:59 am
    Permalink

    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/

    Reply
  • June 19, 2019 at 11:11 am
    Permalink

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

    Reply
  • June 19, 2019 at 11:12 am
    Permalink

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

    Reply
  • June 19, 2019 at 11:15 am
    Permalink

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

    Reply
  • June 19, 2019 at 11:30 am
    Permalink

    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.

    Reply
  • June 19, 2019 at 11:40 am
    Permalink

    Please explain DP using recursion.

    Reply
  • June 19, 2019 at 11:42 am
    Permalink

    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 .

    Reply
  • June 19, 2019 at 11:46 am
    Permalink

    Great video again, thanks a lot

    Reply
  • June 19, 2019 at 2:24 pm
    Permalink

    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?

    Reply
  • June 19, 2019 at 5:11 pm
    Permalink

    Finally some great DP Series going one <3

    Reply
  • June 19, 2019 at 5:50 pm
    Permalink

    Can u suggest some resources for combinatoric with dp,

    Reply
  • June 19, 2019 at 6:09 pm
    Permalink

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

    Reply
  • June 19, 2019 at 7:17 pm
    Permalink

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

    Reply
  • June 19, 2019 at 9:25 pm
    Permalink

    I 1st like your video then see it.

    Reply
  • June 19, 2019 at 9:49 pm
    Permalink

    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.

    Reply
  • June 20, 2019 at 4:02 am
    Permalink

    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.

    Reply
  • June 20, 2019 at 5:15 am
    Permalink

    Thanks for video lectures

    Reply
  • June 20, 2019 at 5:25 am
    Permalink

    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.

    Reply
  • June 20, 2019 at 3:17 pm
    Permalink

    Think "What is important so far"
    First like the video because we know that the video will be good

    Reply
  • June 20, 2019 at 5:21 pm
    Permalink

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

    Reply
  • June 21, 2019 at 2:27 am
    Permalink

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

    Reply
  • June 21, 2019 at 7:00 am
    Permalink

    You simplify the things so easy. Thank u

    Reply
  • June 21, 2019 at 2:24 pm
    Permalink

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

    Reply
  • June 21, 2019 at 3:41 pm
    Permalink

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

    Reply
  • June 22, 2019 at 11:09 am
    Permalink

    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]

    Reply
  • June 24, 2019 at 5:53 am
    Permalink

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

    Reply
  • June 25, 2019 at 7:30 pm
    Permalink

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

    Reply
  • June 26, 2019 at 8:26 am
    Permalink

    I didn't understand any shit

    Reply
  • June 26, 2019 at 1:11 pm
    Permalink

    When the next part will be published? πŸ˜€

    Reply
  • July 1, 2019 at 7:30 pm
    Permalink

    This video is great !

    Reply
  • July 8, 2019 at 12:31 pm
    Permalink

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

    Reply
  • July 25, 2019 at 5:13 am
    Permalink

    make video on segment trees

    Reply
  • July 29, 2019 at 12:29 am
    Permalink

    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.

    Reply
  • August 2, 2019 at 9:48 pm
    Permalink

    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

    Reply
  • August 19, 2019 at 3:25 pm
    Permalink

    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

    Reply
  • August 19, 2019 at 3:31 pm
    Permalink

    Errichto we need the next lecture, please!

    Reply
  • August 23, 2019 at 12:45 am
    Permalink

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

    Reply
  • August 23, 2019 at 8:48 am
    Permalink

    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

    Reply
  • August 23, 2019 at 10:46 am
    Permalink

    Avoid the double counting.
    Avoid the double counting.

    Reply
  • August 23, 2019 at 3:20 pm
    Permalink

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

    Reply
  • August 23, 2019 at 6:16 pm
    Permalink

    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)

    Reply
  • August 24, 2019 at 3:04 pm
    Permalink

    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.

    Reply
  • August 25, 2019 at 1:54 am
    Permalink

    Thanks you to provide this information

    Reply
  • August 27, 2019 at 5:40 pm
    Permalink

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

    Reply
  • August 27, 2019 at 7:34 pm
    Permalink

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

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

    Reply
  • August 30, 2019 at 12:06 pm
    Permalink

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

    Reply
  • September 3, 2019 at 1:40 pm
    Permalink

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

    Reply
  • September 13, 2019 at 4:04 pm
    Permalink

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

    Reply
  • September 22, 2019 at 7:32 pm
    Permalink

    best video ever for learning DP! thanks bro!

    Reply
  • September 29, 2019 at 5:15 am
    Permalink

    love the content, please make videos on backtracking!

    Reply
  • October 4, 2019 at 4:30 am
    Permalink

    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];

    Reply
  • October 21, 2019 at 9:01 pm
    Permalink

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

    Reply
  • October 22, 2019 at 5:32 pm
    Permalink

    You are literally like a god for me right now

    Reply
  • November 5, 2019 at 4:14 am
    Permalink

    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 😁

    Reply
  • November 17, 2019 at 2:47 pm
    Permalink

    How do you come up with relationship?
    for 1…N
    for x in nums
    dp[i] = dp[i-x]

    Reply
  • December 3, 2019 at 1:43 am
    Permalink

    Nice presentation

    Reply
  • December 4, 2019 at 1:03 am
    Permalink

    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.

    Reply
  • January 2, 2020 at 11:31 am
    Permalink

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

    Reply
  • January 3, 2020 at 2:23 pm
    Permalink

    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

    Reply
  • January 11, 2020 at 11:44 am
    Permalink

    Thanks Errichto !!!!!!😊😊😊

    Reply
  • January 21, 2020 at 1:39 am
    Permalink

    Thank you genius ! πŸ˜€

    Reply

Leave a Reply

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