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.
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.
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.
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
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)?
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
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
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.
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.
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]
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?
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.
@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?
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
@@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
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.
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.
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.
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
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).
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
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]?
@@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
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.
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 .
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.
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.
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.
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.
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?
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.
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.
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
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.
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.
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.
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,
@@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.
@@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.
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
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.
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.
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/
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.
Can you make no bug game or any thing in program...how can we make it possible?
Hi, I am really looking forward to the knapsack problem lecture, which should be the 'mother' problem of many problems:)
csacademy problem Closure -csacademy.com/contest/archive/task/and-closure/ uses forward dp approach
Hey, what will change if negative numbers are allowed in the array in first question ?
he seems like the most wholesome .Like the people in anime who are not aware how good they are
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.
"Avoid double counting"
"Avoid double counting"
I double counted the phrase so I guess I have to rewatch
You are an amazing teacher!!
I'm finally starting to understand DP
your videos are so much helpful. please keep up the lectures on DP. liked it very much. Thanks a lot
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.
Thank you so much!!! keep making these type of videos
One of the best videos on DP ever.!!
Finally some great DP Series going one
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
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 !!
Great video! After these DP videos, do videos on graphs please.
I think he should make a comprehensive DP tutorial series with all the things like bitmask, DP optimizations.
@@shoebmoin10 Yes
Erricthto can we have your attention please!
Joma Gave this channel a blow.. and I hope Erri will give some interesting content on it, help many aspiring coders...
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
best video ever for learning DP! thanks bro!
perfect explanation of coin change and double counting
I loved the 'Avoid double counting' joke at the end
You simplify the things so easy. Thank u
Best channel..... Thank You very much..... Keep making videos.
These lectures are gold
Greate! Make a full series of covering different aspects of dp
I love your videos and way you explain. I aspire to be like you at coding!
Great , waiting for tree and graph problem solving series like this.
eagerly waiting for 3rd lecture on dp. errichto u r the best.
Many many thanks for dp series. Hope you will extend this series.
hey errichto please complete the series by discusiing all the basic problems of dp.Just cover the basic 10 -15 problems
Thank you for all these videos plz make videos on combinatorics,number theory,game theory , geometry etc as these topics aren't covered anywhere
Errichto we need the next lecture, please!
Great video again, thanks a lot
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.
You are literally like a god for me right now
Calling people god is so cringe.
@@llliiilll3624 Nope.
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)?
This is very helpful.Thank you very much.
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
Thanks.
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
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.
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.
just write an if condition to avoid out of bounds errors like : if (i - x) >= 0 or maybe x
What is Errichto talking about @15:15? Can anybody please explain?
Thanks a lot. Keep up the good work. Take love
Can somebody help me to provide the code for third problem , by method errichto taught.
I couldn't understand that
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]
Thanks for sharing young Master
Love your videos. When will you make the third video on DP, Looking forward to it.
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?
Thanks for video lectures
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.
dp[0] = 0;
for(int i = 0; i < denominations.size(); i++)
for(int current_sum=denominations[i]; current_sum
How do you come up with relationship?
for 1...N
for x in nums
dp[i] = dp[i-x]
Just apply what is allowed in the statement. Also, I don't know what part you're refering to. Always put a timestamp.
@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?
@@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?
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
@@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
Thanks Errichto !!!!!!😊😊😊
Great video Errichto! Would love to see the famous egg drop problem.
This video is great !
love the content, please make videos on backtracking!
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.
Nice presentation
What if values of array are in double instead of integer then how you will take that sum as indices of dp array?
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.
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.
@@lichangyu5768 牛逼，看完视频对那部分还是有点疑惑，看完你的解释我终于悟了。多谢大哥。
hey i am not able to follow. where can i see implementation
should not dp[0]=0 in the min. number of denominations case?
Thanks you to provide this information
saw you on JOMA had to subscribe and hit the bell icon!
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
?
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
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 :)
Really good video!! Can you please make some video of dp bitmask
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
Plz make a series on graph theory
how does the code for second problems work? i don't get it
Hi errichto, what exactly do we return when i-x falls out of bounds , below 0?
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).
@@Errichto thank you Kamil!
When the next part will be published? :D
Avoid the double counting.
Avoid the double counting.
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?
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
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]?
@@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
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.
hey errichto why did you stop your dp series man.Please continueeee it.We need it
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 .
We don't go backwards. We go from 1st or 0th.
And why are you asking here instead of that first episode? ;p
There are two broad styles of DP, backward and forward. Usually, you can choose whatever feels more intuitive to you.
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.
@errichto can you please provide some read-up resources for forward or push dp?
@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.
I guess maybe the explanation @2:37 is the best way to think about it???
@@EzraSchroeder do you still have that doubt
Can u suggest some resources for combinatoric with dp,
last slide->
*Avoid double counting
*Avoid double counting
You madlad errichto!
can someone please explain forward dp its bit confusing pls
for coin change (min) what would happen if you init dp[1..N] = 0?
Does anybody know how to choose between backtracking and dynamic programming - problem's definition are similar how to choose one or another approach?
Thank you genius ! :D
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.
Say please, what painting app are you using?
I 1st like your video then see it.
how to find the pattern to get the state and recurrsion? Can you please elaborate it?
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.
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.
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.
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?
It's hard to rate the difficulty of so standard (well known) problem. I guess it's div2-B.
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.
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.
why are we not considering double counting in min coin change problem ?
so the third problem (coin change - ways) is basically two steps of JUMP and ACTUALLY USE
THANK YOU
@errichto subtitles are covering the algorithms
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
It's ok for beginners and your question was asked thousands of times, use Google next time.
@@Errichto Thanks so much sir, i am continuing my coding in python after your reply
Thank you
@@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
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.
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.
You lost me at the pseudo-code and I've already solved this problem more than once.
same, I am very lost at the code. It should be explained much clearly, if the viewer is unfamiliar.
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.
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,
@@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.
@@Errichto OK!
@@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.
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
You wrote "avoid double-counting" twice. Oh, nevermind.
dp[i] += dp[i - x] in combination sum will give negative index, so how ?
add a condition if(i>=x). that is just a pseudocode
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.
But how about when the SUM... is 41?
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.
Please explain DP using recursion.
I prefer iterative dp. I explained why in the first lecture.
@@Errichto but considering your viewers you should also explain it using recursion it would be very helpful.
@@youtubeuser5822 There are hundreds of blogs and videos about recursive dp and barely anything about iterative dp. Why would I do recursion then?
@@Errichto 😟
@@Errichto yup iterative solutions are hard to find, even for graph, trees algos.