Dynamic Programming lecture #2 - Coin change, double counting

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

[@chatrughanprasad7778]

perfect explanation of coin change and double counting

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

[@amritbhardwaj99]

One of the best videos on DP ever.!!

[@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

[@kishansinha5005]

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

[@lekdendorji6a]

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

[@svapnilsawant116]

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

[@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

[@rimurusama5070]

These lectures are gold

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

[@RishabhDeepSingh]

Finally some great DP Series going one

[@val5_]

You are literally like a god for me right now

[@llliiilll3624]

Calling people god is so cringe.

[@jayantjha3128]

@@llliiilll3624 Nope.

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

[@kishantiwari3221]

You simplify the things so easy. Thank u

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

[@lovvyparhar393]

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

[@rahulbhatia1313]

best video ever for learning DP! thanks bro!

[@progamerzzz1237]

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

[@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]

[@rajansaharaju1427]

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

[@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

[@DHRUVNARAYANSINGH]

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

[@Chakradhar26]

Errichto we need the next lecture, please!

[@amangupta-el1gf]

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

[@pranav4592]

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

[@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

[@vivekpal1004]

Avoid the double counting. Avoid the double counting.

[@sarveshdubey9347]

Great video again, thanks a lot

[@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

[@diegonayalazo]

Thanks for sharing young Master

[@pradyumnakatageri3475]

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

[@sumantopal558]

Thanks for video lectures

[@CarrotCakeMake]

Nice presentation

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

[@MehbubulHasanAlQuvi]

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

[@shnerdz]

love the content, please make videos on backtracking!

[@sudheertripathi3882]

Thanks Errichto !!!!!!😊😊😊

[@augustinekanyi]

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

[@ronnith2405]

Plz make a series on graph theory

[@Gynormousdish]

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

[@jamilahmedahmed8187]

Thanks you to provide this information

[@rahulsingh40g]

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

[@sonitushar93]

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

[@vatsalsonigara3707]

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

[@wizardOfRobots]

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

[@amolmishra7891]

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

[@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

[@sridharbajpai420]

make video on segment trees

[@fbru02]

This video is great !

[@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

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

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

[@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?

[@cliid4355]

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

[@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)?

[@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 牛逼，看完视频对那部分还是有点疑惑，看完你的解释我终于悟了。多谢大哥。

[@sharp615]

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

[@progamerzzz1237]

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

[@manjumallesh6932]

@errichto subtitles are covering the algorithms

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

[@madelineabio9406]

THANK YOU

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

[@amansingh-os9gd]

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

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

[@sayan8635]

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

[@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

[@geoffl]

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

[@azzzn-m8h]

how does the code for second problems work? i don't get it

[@codingwithanonymous890]

can someone please explain forward dp its bit confusing pls

[@omti]

When the next part will be published? :D

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

[@VishalJangid1]

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

[@Chandansingh374]

Can u suggest some resources for combinatoric with dp,

[@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?

[@youtubeuser5822]

Please explain DP using recursion.

[@Errichto]

I prefer iterative dp. I explained why in the first lecture.

[@youtubeuser5822]

@@Errichto but considering your viewers you should also explain it using recursion it would be very helpful.

[@Errichto]

@@youtubeuser5822 There are hundreds of blogs and videos about recursive dp and barely anything about iterative dp. Why would I do recursion then?

[@youtubeuser5822]

@@Errichto 😟

[@pushkarsoni8927]

@@Errichto yup iterative solutions are hard to find, even for graph, trees algos.

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

[@aurrum4654]

Say please, what painting app are you using?

[@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 ?

[@Makitotutosgamemaker]

Thank you genius ! :D

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

[@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

[@Sharkistas]

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

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

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

[@EzraSchroeder]

@2:14 how do you know dp[0] = 1? I used to be much better at math & even have a B.S. degree in it, but don't remember much.

[@EzraSchroeder]

I guess maybe the explanation @2:37 is the best way to think about it???

[@LadderVictims]

@@EzraSchroeder do you still have that doubt

[@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

[@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]?

[@jimmyshenmusic]

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

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

[@Vins-pe8mw]

i dont get how you got the sequence 1,0,0,0,0 in min 3:00 i=1 , then: dp[1] += 1-1 + 1-2 + 1-3 = -2 ?

[@suryasuresh9330]

hmm good catch, I believe he forgot another condition probably, the code makes more sense if there was an if statement that breaks when i - x < 0, that way it doesnt go into the negatives

[@md.romizulislam7416]

he didn't complete bro, don't dare to find wrong of a LG he was just trying to ease and showing the way to solve , not the solution :)