Dynamic Programming lecture #2 - Coin change, double counting

Part 1: • Dynamic Programming le...
This is the second of several lectures about Dynamic Programming. I will again go through three problems: Combination Sum, Coin Change (min) and Coin Change (count). The third one is hardest because of double counting. Links to Leetcode in the pinned comment. Watch this lecture if you practice for competitive programming or for coding interviews. Consider turning captions on and setting the speed to x1.25.
Please give me suggestions about the format of a lecture or about topics for future lectures.
- Frequently Asked Questions: github.com/Err...
- Github repository: github.com/Err...
- Facebook: / errichto
- Twitter: / errichto
- Competitive Programming Discord: discordapp.com...
- KZbin channel 1: / errichto (mainly short videos)
- KZbin channel 2: / errichto2 (streams)
I’m Kamil Dębowski, better known as Errichto. I compete in and organize programming competitions. I make educational streams on KZbin and Twitch. I'm a finalist of ACM-ICPC, Topcoder Open, Facebook Hacker Cup and Google Code Jam. I got a second place in Google Code Jam 2018. I am/was nutella in Codeforces and target in Topcoder.
Watch me if you want to practice for coding interviews, competitive programming or just algorithms in general. I share my thought process, explain everything, and mention similar problems and techniques/algorithms.

[@Errichto]

Combination sum - leetcode.com/problems/combination-sum-iv/ Coin change (min) - leetcode.com/problems/coin-change/ Coin change (count) - leetcode.com/problems/coin-change-2/

[@yuvrajgarg3921]

Hey can you please guide me how I can combine Algorithms with Probability and Statistics. I knew Algorithms I knew probability but dint knew how to combine them.

[@masternobody1896]

Can you make no bug game or any thing in program...how can we make it possible?

[@tianyangren]

Hi, I am really looking forward to the knapsack problem lecture, which should be the 'mother' problem of many problems:)

[@siddharthabhi8704]

csacademy problem Closure -csacademy.com/contest/archive/task/and-closure/ uses forward dp approach

[@harshmishra7768]

Hey, what will change if negative numbers are allowed in the array in first question ?

[@progamerzzz1237]

he seems like the most wholesome .Like the people in anime who are not aware how good they are

[@SuperSam4y0u]

I went over this video 10-12 times for the last 2 days to understand the `why does it work` part rather than `how to solve` and finally I think I understand. Probably nobody else on youtube explains the small details which you do. Thanks for sharing your knowledge Kamil, really appreciate it.

[@enzodantas4072]

"Avoid double counting" "Avoid double counting" I double counted the phrase so I guess I have to rewatch

[@shivangitomar5557]

You are an amazing teacher!! I'm finally starting to understand DP

[@alamintushar5824]

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

[@naughtyrishan]

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.

[@wizardOfRobots]

last slide-> *Avoid double counting *Avoid double counting You madlad errichto!

[@mridul1161]

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

[@lekdendorji6a]

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

[@Hetp111]

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

[@shoebmoin10]

I think he should make a comprehensive DP tutorial series with all the things like bitmask, DP optimizations.

[@chinmaym7479]

@@shoebmoin10 Yes

[@mohammedajaaz8694]

Erricthto can we have your attention please!

[@piyushnaithani7689]

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

[@akramelomrani8728]

I can't say no but regardless errichto had + 150k subs before that video so we shouldn't say that he wouldn't succeed without that collab

[@svapnilsawant116]

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

[@fractal_lynn]

The coin change problem is what led to me to realize that I needed to learn dynamic programming. Thank you for going over this, your explanations are always crystal clear :D

[@RishabhDeepSingh]

Finally some great DP Series going one

[@progamerzzz1237]

hey errichto please complete the series by discusiing all the basic problems of dp.Just cover the basic 10 -15 problems

[@amritbhardwaj99]

One of the best videos on DP ever.!!

[@pranav4592]

I love your videos and way you explain. I aspire to be like you at coding!

[@prajwalchoudhary4824]

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

[@chatrughanprasad7778]

perfect explanation of coin change and double counting

[@rahulbhatia1313]

best video ever for learning DP! thanks bro!

[@rajansaharaju1427]

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

[@kishantiwari3221]

You simplify the things so easy. Thank u

[@debjit811]

The last problem "Count Coin change" can be solved in a much simpler way using 1D array: dp[0] = 1; for x in nums: for i from (1 to x): dp[ i ] += dp[ i - x ]; print dp[x]

[@amangupta-el1gf]

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

[@DHRUVNARAYANSINGH]

Great , waiting for tree and graph problem solving series like this.

[@peepforlearning6058]

in coin change(min) problem, to overcome negative index use, if(i-x < 0 ) break; inside the for x in nums, before checking the min.

[@lovvyparhar393]

Best channel..... Thank You very much..... Keep making videos.

[@kishansinha5005]

I loved the 'Avoid double counting' joke at the end

[@val5_]

You are literally like a god for me right now

[@llliiilll3624]

Calling people god is so cringe.

[@jayantjha3128]

@@llliiilll3624 Nope.

[@Chakradhar26]

Errichto we need the next lecture, please!

[@rimurusama5070]

These lectures are gold

[@sarveshdubey9347]

Great video again, thanks a lot

[@jingrenlim1897]

This is very helpful.Thank you very much.

[@YashSingh-ir3ec]

To avoid Double Counting I think this could work well. If we have currently denomination i, then I could make the sum greater than or equal to i using this denomination so that we will have all denominations required for a particular sum in non-decreasing order. This will reduce double counting. So using only one state we could solve this problem i.e sum only.

[@YashSingh-ir3ec]

dp[0] = 0; for(int i = 0; i < denominations.size(); i++) for(int current_sum=denominations[i]; current_sum

[@pradyumnakatageri3475]

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

[@shnerdz]

love the content, please make videos on backtracking!

[@Gynormousdish]

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

[@sudheertripathi3882]

Thanks Errichto !!!!!!😊😊😊

[@sumantopal558]

Thanks for video lectures

[@sharinganuser1539]

while watching this....i got something in my mind but i don't know if its correct... if in a dp you have to make choices....most of them will be either fibonacci , 0/1 knapsack or unbounded knapsack.(how to distinguish which one?) 1)if order dosen't matter for your choices and how many times u want an item also dosen't matter then its fibo 2) if order matters and you can take an item only once then its 0/1 knapsack 3) if order matters , u can take an item any number of time its unbounded knapsack.

[@himanshusekharsahoo9269]

While solving Combination sum : leetcode.com/problems/combination-sum-iv/ you might encounter a few issues with overflow here is a blog for your help : leetcode.com/problems/combination-sum-iv/discuss/1144739/How-signed-integer-overflow-happened

[@MehediHasan-rq3fs]

Thanks.

[@my3m]

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

[@Errichto]

Just apply what is allowed in the statement. Also, I don't know what part you're refering to. Always put a timestamp.

[@rafay6821]

@errichto at around 4:30 when you provided the dp relation dp[ i ] = dp[ i - x ], could you please say why i-x? What is the justification behind it. Or more specifically what thought process went behind deriving that relation?

[@neowitcherrivian3594]

@@Errichto at 3:03 you defined the dp relation to be dp[ i ] += dp[ i - x ], could you please explain how did you come up with it?

[@cindytrinhsridykhan6375]

The way I understand it: The idea is to go through each element x of the array nums and see how many ways you can come up with if you construct a sum starting with x. If we take the example of the video: nums = [1, 2, 3] and N = 4. Assume that we have filled all the elements of dp for i

[@suryasuresh9330]

@@cindytrinhsridykhan6375 thank you this made a lot of sense! I feel this part of the problem solving is the toughest to come up with. He came up with the answer without really explaining where he got the intuition from

[@MehbubulHasanAlQuvi]

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

[@fbru02]

This video is great !

[@diegonayalazo]

Thanks for sharing young Master

[@jamilahmedahmed8187]

Thanks you to provide this information

[@augustinekanyi]

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

[@amolmishra7891]

should not dp[0]=0 in the min. number of denominations case?

[@madelineabio9406]

THANK YOU

[@sonitushar93]

What if values of array are in double instead of integer then how you will take that sum as indices of dp array?

[@CarrotCakeMake]

Nice presentation

[@rahulsingh40g]

Can somebody help me to provide the code for third problem , by method errichto taught. I couldn't understand that

[@vatsalsonigara3707]

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

[@farhan787]

Kamil what is 'k' at 10:21, is k the largest number in coins array? You said 'k' is the number of them(coins) so is it the size of array and if it's then isn't it k == n (size of coins array)?

[@di3g04]

You lost me at the pseudo-code and I've already solved this problem more than once.

[@AlexandrBorschchev]

same, I am very lost at the code. It should be explained much clearly, if the viewer is unfamiliar.

[@ajr1791ze]

I 1st like your video then see it.

[@ronnith2405]

Plz make a series on graph theory

[@Makitotutosgamemaker]

Thank you genius ! :D

[@vivekpal1004]

Avoid the double counting. Avoid the double counting.

[@shreyanshsingh2627]

Could you do a video on linear data structures? Like, standard problems on them and the intuition behind how to solve problems related to them?

[@wizardOfRobots]

Was initially confused because the numbers in the example were 1,2,3 . For anyone else confused, take a different set of numbers and you'll understand faster.

[@yogendersingh4154]

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 .

[@Errichto]

We don't go backwards. We go from 1st or 0th. And why are you asking here instead of that first episode? ;p

[@getintodevices1215]

There are two broad styles of DP, backward and forward. Usually, you can choose whatever feels more intuitive to you.

[@getintodevices1215]

So for staircase problem, define f(x) as ways to cover x stairs ahead of us. Then f(x) = f(x - 1) + f(x - 2). Ways to cover x - 1 stairs ahead of us(jump 1 stair) + ways to cover x - 2 stairs ahead of us(Jump two stairs). There can be other ways to think of this and it depends on whatever feels natural to you.

[@cliid4355]

so the third problem (coin change - ways) is basically two steps of JUMP and ACTUALLY USE

[@soumyajeet7809]

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?

[@Errichto]

It's hard to rate the difficulty of so standard (well known) problem. I guess it's div2-B.

[@scofield1154]

You can count that famous problems like these will never appear in a contest, at least in this format. Its entirely possible to get a problem in a contest which solution requires a similar dp solution to one of these famous problems, but you will never encounter a problem that asks you this kind of a problem in a contest.

[@getintodevices1215]

There are similar problems in CF set as Div 2C, but they have statements which make them harder and also require some observation to arrive at recurrence. For ex, codeforces.com/contest/456/problem/C this problem is well known, but CF version is bit difficult in terms of observing the recurrence.

[@TheDarkaqua]

6:39 the problem with ``dp[i] = min(dp[i], dp[i-x]+1)`` seems that if the coin denomination i.e 'x' is greater than N then it breaks eg: nums=[1,10] and N=4 the array should have 1 coin i*1 times =[0,1,2,3,4] but since we do dp[i-x] i.e dp[1-10] i get an list index out of range error in python. correct me if i'm wrong, thanks

[@mr.l6332]

I was also wondering if there is an elegant solution for that issue (it also appears earlier in the vid at 3:15). A clumsy solution would be to populate the first couple of elements in dp[] with extra logic attached to avoid negative indexes, and then run the program as normal, but there has to be a better way right? For 3:15 the forward-working dp avoids the issue, but I naturally tend to think of problems in the backwards-working way, so I hope someone can share a solution.

[@mr.l6332]

Oh nvm, he explains in the video that an actual implementation of the pseudocode would require logic statements to make sure (i-x) >= 0 and that values of dp need to be initialized to their respective amounts.

[@harshmishra7768]

just write an if condition to avoid out of bounds errors like : if (i - x) >= 0 or maybe x

[@hakankanplay]

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.

[@sridharbajpai420]

make video on segment trees

[@blazer511]

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

[@Errichto]

It depends on a problem. If it's counting ways to achieve something, then 0 (there are zero ways to get negative sum). If it's maximizing some value, then -INF (so that it wouldn't affect the answer).

[@blazer511]

@@Errichto thank you Kamil!

[@getintodevices1215]

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.

[@manjumallesh6932]

@errichto subtitles are covering the algorithms

[@lobsanggyatso6280]

Can u tell me when to call recursive function inside loop or not. I saw in one video that suggest that most often permutation are used with loop

[@nsarda]

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.

[@lichangyu5768]

It seems bit cutoff. But what he meant is, if we use the lastCoin as the second state, it is impossible going from (17, 2) to (17, 3). Thus you have to count (17, 2) - > (20, 3) and (17, 3) - > (20, 3) separately even (20, 3) is the same state because there are two distinct path leading to that state. However, if you allow the transition (17,2 ) - > (17, 3) by redefining the second state as limit of coin ranged has been used, then you have to count (20, 3) only once because if you go (17, 2) - > (20, 3) or (17, 2) - > (17, 3)- >(20, 3) should leads to the same state(transitivity and thus a cycle). But then you have to redefine all the recursive relationship, which is the usual coin- change algo that you can find online.

[@nishuone161]

@@lichangyu5768 牛逼，看完视频对那部分还是有点疑惑，看完你的解释我终于悟了。多谢大哥。

[@ajr1791ze]

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.

[@ariabanazadeh1016]

Yes but 2 is hidden in 3 and 1. Because if we want to pick it and go to next index it's like that we pick it and remain at the same index and in the next state, we don't pick it and go to next index. Sorry for my bad English,

[@Errichto]

@@ariabanazadeh1016 Yup, exactly. 1 and 3 are enough. States and transitions create some graph. By adding that second case you would create unnecessary edges. There is path A->B->C and you're trying to add an extra edge A->C that represents the same thing.

[@ajr1791ze]

@@Errichto OK!

[@ariabanazadeh1016]

@@Errichto Can you give us a list of good dp problems( I mean with good ideas There is alot of dp problems in code forces and if i sort them by solved count there will be a lot of same ideas or there will be to hard or to easy) so if you have a list of good dp problems please give me. Thank you very much.

[@VishalJangid1]

You wrote "avoid double-counting" twice. Oh, nevermind.

[@progamerzzz1237]

hey errichto why did you stop your dp series man.Please continueeee it.We need it

[@indrajitbanerjee5131]

@errichto, the content is really good, but most of the programmers face difficulties while building a dynamic programming solution is to find out the "nutcracker!" the dp condition which makes it dynamic in nature. Can you please make a video on that, like how to quickly think over a "DP" model, and how can we more generalize it?

[@Errichto]

I don't know what you're talking about. I explained how I think about dp problems.

[@AlexandrBorschchev]

No, I think it's a good question. The answer is practice and solve more problems, read editorials...Well, first you need to know all classical dp problems as this is the prerequisites. I think there are some tutorials and blogs on topics such as invariant, states, etc. but learning them is just as important as seeing patterns and getting intution from solving many many dp problems.

[@amansingh-os9gd]

hey i am not able to follow. where can i see implementation

[@sharinganuser1539]

it was initially difficult to understand the O(n.k) of coin change....to understand that its good to think with an example... lets say coins:1,2,3 and sum=7 and we are on last block of our grid i.s dp[coin=3][sum=7] its enough to think no.of ways to get (sum=7 and coin=2) +(sum=7-3 and coin=3) therefore dp[3][7]=dp[2][7]+dp[3][7-3=4] // just take care of base case...and u r good to go.

[@alihamdar5916]

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]

[@randomrandom316]

Suppose you want the number of ways of getting sum as 8 and you have 1,2 or 3 to choose from. dp[8] = dp[7]+dp[6] + dp[5] means to get sum equals to 8 since we have only 1,2,3 to work with if you are already at sum 5 you could add another 3 to get to 8 or if you were at 6 you could add another 2 to get to eight or else if you were at 7 you could add another 1 to get to 8. I hope this helps.

[@emilmohaneriksson]

I was also confused by this at first. But I think the recursive formula is very similar to the counting steps formula. If you imagine a staircase with i steps and that you are only allowed to take 1, 2 or 3 steps at a time. Then you can ask yourself, what are the number of ways to reach the top? This is analogues to the original question. Thus if we are required to reach the top we must first reach one of the three preceeding steps i.e. step i-1 , i-2 or i-3. Trivially these three scenarios do not overlap and we can be sure that we have counted all the possibilities. Thus dp[i] = dp[i-1] + dp[i-2] + dp[i-3] for any i>=3.

[@K_RNDM]

not getting how you moving from state 17, 1 to 17, 2 for 16:20? if last coin used is of index 1 and sum is 17 then from that point using coin of index 2 how is landing me to state 17, 2?

[@shrad6611]

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

[@sharp615]

What is Errichto talking about @15:15? Can anybody please explain?

[@sayan8635]

@errichto can you please provide some read-up resources for forward or push dp?

[@geoffl]

for coin change (min) what would happen if you init dp[1..N] = 0?

[@calvinwijaya9706]

dp[i] += dp[i - x] in combination sum will give negative index, so how ?

[@vaibhavahuja4001]

add a condition if(i>=x). that is just a pseudocode

[@Chandansingh374]

Can u suggest some resources for combinatoric with dp,

[@codingwithanonymous890]

can someone please explain forward dp its bit confusing pls

[@arpanlayek6405]

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

[@ivan-e-t5h]

Does anybody know how to choose between backtracking and dynamic programming - problem's definition are similar how to choose one or another approach?

[@vairamuthu2748]

why are we not considering double counting in min coin change problem ?

[@abhisheksa6635]

One question for the first example as to how we are getting dp[0] = 1 coz truly there is no way to get 0 with [1,2,3] but if we see dp[1] = 1 which sounds reasonable, does this poses a fundamental issue in thinkin.

[@utkarshtyagi8716]

I think dp[0] = 1 refers to the case where we dont choose any number out of the given array, since we can choose a number 0 times or multiple and in case of dp[0] we chose every number 0 times. Hope this helps.

[@philosphize]

Sir can you please say , i have started coding in python but most of people do competitive coding in c++, should i quit python and shift in c++ or I should continue my coding in python itself

[@Errichto]

It's ok for beginners and your question was asked thousands of times, use Google next time.

[@philosphize]

@@Errichto Thanks so much sir, i am continuing my coding in python after your reply Thank you

[@philosphize]

@@Errichto i did google but i was just thinking if a pro coder like you will advise me then its would be more enthusiastic for me to do so

[@hound4425]

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.

[@splytrz]

3:28 isn't the first solution wrong? If the array of allowed numbers is, say, [3, 5, 6], then when i = 1 we will try to get dp[1-3] which is out of range.

[@peepforlearning6058]

i too have same doubt, in c the negative index is set default to zero in an array. i accept an array index start from o, we not deeply understood, a[i] or (a+i) by which we understand, a point to start address of the array, and we save the data to the incremented address only, so +i allow us to point to next element, -1 which denoted as before starting the array address some other point. which will be zero or a garbage value, most compiler says zero, and we don't encounter with any error by using it.

[@abdelrhmansamir1426]

He mentioned that it's a pseudo code code. you can use if condition to make sure that you 're not out of boundary that's all.

[@AlexandrBorschchev]

am i too stupid or everything just flew past my head? I feel it's too fast, am I supposed to know something before watching this video?

[@saikiran-ws2oc]

Good

[@omti]

When the next part will be published? :D

[@Sharkistas]

But how about when the SUM... is 41?

[@dmitrydmitriev2554]

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

[@dmitrydmitriev2554]

It's looks like transition (sum:17, last_coin: 2) => (sum: 17+2, last coin:2) or (sum: 17+3, last coin: 3). But why do 3 and 2 some times written like nums[2] or nums[3]?

[@jimmorrisshen]

@@dmitrydmitriev2554 I had the similar doubt. I read the leetcode discussion and wrote a summary here. Hope it helps. medium.com/@jim.morris.shen/combination-sum-or-coin-change-cd9264a02903?source=friends_link&sk=f071a05acbedc48a1ce9b1f61b5f49ab