i has been struggling to do programming but i never gave up and it's been 3 months of regular coding i learn something new everyday .. Its not too late to do it
It is very important to look at concepts from all the possible perspectives in order to get a better understanding and to be able to solve very different problems. This was such a nice video that explains a beginner level problem from all the angles. Thank you Kamil
A very insightfull approach to teaching dynamic programming. I'd love to see a video about some advanced dp optimizations, like divide and conquer dp, or convex hull trick.
The video covered wide variety of approaches and did require a lot of thinking on viewer part as well. Thanks @errichto for creating such great educational content.💫
Errichto you are the best bro you have the talent and the way to teach others your knowledge that's simple beautiful when someone explains complex things easily, I really love this dynamic programming series I'll be waiting the 4th lecture, please take it on consideration. Good vibes Errichto.
Laughed a lot at the ending: "I hope you understood all the 3 solutions ... If not, try watching the video again." 😂😂😂 Yes, sir, I did it a few times until finally got it. Great video btw
Thanks for the nice video! I struggled a bit with the order of states described at 15:10. Thus, I would offer an easier-to-understand and more natural order of computing solution I (bottom-up) (mentioned at 5:00 and presented at 15:10). Based on the understanding that the profit for a row of length K is only dependent on the profits of rows of length K-1, the outer loop could go from length in 2..N, since we deal with rows of length 1 as part of the initialization. The inner loop then goes from L in 1..(N-length+1). Then, R simply equals left + length - 1 and dp[L][R] is computed as before.
Hi, Errichto. As always great video, and lots of high value material. I have a problem though, when you compute the year: For the first year, L=1, and R=N, for the second year either (L=2 and R=N) or (L=1 and R=N-1). With your formula Y=N-(L-1)-(N-R), I can't find the correct answer. Should the fomula be Y = L + (N-R)? Or do I miss something?
Oh, you are right. My formula computes the length of the interval [L, R] in some complicated way. It would work for solution III, but not here. Thanks for spotting a mistake!
Nice problem! When solving I came up with a different solution to Errichto's solutions. Instead of dp variables L and R I used variables L and year. In this case dp[L][year] denotes what is the maximum we can earn by the given year if L left wines are sold. Initialization is dp[L][year]=0 and the progression is push style, from the current year to the next. Nice property of this solution is that only the last year needs to be stored (i.e, resulting in O(N) memory). It is quite intuitive to implement as the DP progresses through time (years).
@Errichto . Please make more and more dp videos like your previous dp videos including these with complete thought process.Also make series of videos for graphs from beginning to advanced. I completely like your way of teaching. I want more and more videos should be out by you so that I can think like you in every problems.
WOW... theese three DP tutorials you made are so inspiring. I was struggling in algorithm course and the lecturer in my uni don't explain the thinking process. After watching these three tutorials you made, I solved all the DP problems in the assignment
I’ve tried around 30 DP problems on leetcode and watched tons of lectures on DP as well including yours but I’m still not able to identify what should be the state(here sum) and what should be the parameters(here L,R). As you said you can simply keep what is asked in the question to be the state say maximum value or number of sets. But i have a really hard time deciding what the parameters for a state should be. Even if it obvious sometimes. Also I have difficulty with iterative solutions as you showed in this example we should have L+1 computed so the arrow should be N to 1 which I’m not able to think on my own. What do you suggest I do about it? Is there a resource I can study from to understand what I’m missing better or practice makes perfect? Thanks. :)
hi Errrichto, I was wondering about the top down solution of this problem. So if dp[L][R -1] = dp[L][R] + P[R].Y then dp[L + 1][R] = dp[L][R] + P[L].Y right? So isnt it that I have to implement two separate formula in an iterative method? Like do I need to have 2 separate for loops, 1 for dp[L][R - 1] and 1 for dp[L + 1][R] ? Thanks in advance : D
Awesome video, very helpful stuff! I am struggling with the implementation for the bottom up approach, is there any chance you could show me the full code for this implementation. Thanks! love your videos
Is there a systematic way to determine if a problem should be approached with greedy vs DP? Or do you just try to work through the example with greedy, and if it breaks, move on to DP? If the provided example still works for greedy it might be tricky to find a contradiction.
Approach 3 will be a good solution if the problem is changed to a stream problem where you do not know the size of the array initially, as the solution doesn't depend on the array size. Approach 1 and 2 are dependent on size of array
can you make next video about dp with strings like maximum substring with all distinct characters in a string or minimum length of substring containing all characters in original string. I don't know how to approach these kind of problems one of my colleage said it could be done by dp[N][26] but i would like to know the thinking process.
Found out about you from Joma Tech. During the interview you mentioned that your strong math background helped you skyrocket through Cormen's algorithms book. Specifically what math books in what specific math subjects did you study prior to learning algorithms from the Cormen book? Thanks!
@@Errichto Thanks man! Totally subscibed👍 Do you have any advice on what are the specific math subjects you find important to know prior to hitting the algorithms book?
Has anyone found where can we practice this problem? I found it at Codechef, but it says "The contest problem is not available for accepting solutions).
Nice explanation, I am starting with dp. So as a beginner, I compute the result with the greedy approach. From here how I am supposed to think that the greedy approach will not be the optimal one? Do I first code it out and then think of Dp or just take smaller examples and see from hit and trail that greedy breaks and I should go for dp?
You should think: how would this greedy approach be correct? Can making this decision now hurt me in the future (after a few steps)? If yes, maybe let's try to create a counterexample. It's a bit of intuition plus thinking about proof or counterexample.
Hey Errichto, great tutorial! Do you have the actual code for this exercise? I understood the big picture but im still a bit confused on the actual implementation. Much appreciated.
hey i find clrs very tough as its questions are too mathy(atleast for me) any suggestion? should i improve on my math knowledge an stick to clra or find some other book(in this case plz do recommend one)
I love coding but when i dont know a solution to a problem i open editorial or other submissions and learn the algorithm and implement it . Does this help or should try even more to get the solution on my own . Thanks keep up your good work.
Just make sure to try to do it yourself first. Then it's good to check the editorial and learn what is the solution. Read more here: github.com/Errichto/youtube/wiki/How-to-practice%3F
@@AshikaUmanga Maybe I will do it. Now you can read about it here: codeforces.com/blog/entry/43256 (part about "Recovering the best solution for optimization problems ")
What kind of question is this ;p you need some brain capacity to do any job that requires thinking. It doesn't mean you have to be a genius to become a programmer.
Pls hit the bell button. And subscribe to my 2nd channel for very boring streams: th-cam.com/users/errichto2
Done.
Please keep making DP videos they're really helpfull.
They are not boring sir , they are actually very helpful , thanks again
Where is link for leetcode question?
Implementation www.hackerearth.com/practice/notes/dynamic-programming-i-1/
i has been struggling to do programming but i never gave up and it's been 3 months of regular coding i learn something new everyday .. Its not too late to do it
This is great !! Really you have a gift for explaining . Watched the video at 1.5x and it was perfect speed.
It is very important to look at concepts from all the possible perspectives in order to get a better understanding and to be able to solve very different problems.
This was such a nice video that explains a beginner level problem from all the angles. Thank you Kamil
Please, keep uploading videos on this topic. Your videos are so useful.
The first 3 parts were great :D
Waiting for the 4rth one
A very insightfull approach to teaching dynamic programming. I'd love to see a video about some advanced dp optimizations, like divide and conquer dp, or convex hull trick.
Heyyy just got in to MIT, thank you for helping me so much. Looking forward to building some fun stuff :D
Dude appreciate your Work.
I bet no one can explain dynamic programming terms and ways to solve it more patiently and clearly.
The best. Much much better than those who only try to sell their websites or product.
Hey guys!! Just to make sure you get it, at 14:06 it's "year 1" instead of "interval 1". Enjoy!!
The video covered wide variety of approaches and did require a lot of thinking on viewer part as well.
Thanks @errichto for creating such great educational content.💫
Errichto the mvp
Big thank you for spending the time in making this video. Very well explained. Enjoyed it. :)
Very good explanation
Errichto you are the best bro you have the talent and the way to teach others your knowledge that's simple beautiful when someone explains complex things easily, I really love this dynamic programming series I'll be waiting the 4th lecture, please take it on consideration. Good vibes Errichto.
I am very grateful to you.From Bangladesh
Create a playlist of "Dynamic Programming Lectures".
It will be easier for us to find the tutorials.
Good idea, will do that tomorrow!
@@Errichto sir, Will you make more videos on Dynamic programming ??
Sir you should continue this series.We are larning a lot
Laughed a lot at the ending: "I hope you understood all the 3 solutions ... If not, try watching the video again." 😂😂😂
Yes, sir, I did it a few times until finally got it. Great video btw
good that you gave recursive intution this time along with iterative. pls. continue it.
Thanks for the nice video! I struggled a bit with the order of states described at 15:10. Thus, I would offer an easier-to-understand and more natural order of computing solution I (bottom-up) (mentioned at 5:00 and presented at 15:10). Based on the understanding that the profit for a row of length K is only dependent on the profits of rows of length K-1, the outer loop could go from length in 2..N, since we deal with rows of length 1 as part of the initialization. The inner loop then goes from L in 1..(N-length+1). Then, R simply equals left + length - 1 and dp[L][R] is computed as before.
Thanks for the nice problem and great explanations !
Thanks for sharing young Master
8:13 How is the L-1 case handled? We're only considering removal from right but not left
Hi, Errichto. As always great video, and lots of high value material. I have a problem though, when you compute the year: For the first year, L=1, and R=N, for the second year either (L=2 and R=N) or (L=1 and R=N-1). With your formula Y=N-(L-1)-(N-R), I can't find the correct answer. Should the fomula be Y = L + (N-R)? Or do I miss something?
Oh, you are right. My formula computes the length of the interval [L, R] in some complicated way. It would work for solution III, but not here. Thanks for spotting a mistake!
@@Errichto it'd be really helpful if you could provide the code for all 3 implementations of this problem.
Thank you so much errichto..
make this series more active, atleast 1-2 episode every week
I will do my best but can't guarantee 1-2 episodes weekly.
Nice problem! When solving I came up with a different solution to Errichto's solutions. Instead of dp variables L and R I used variables L and year. In this case dp[L][year] denotes what is the maximum we can earn by the given year if L left wines are sold. Initialization is dp[L][year]=0 and the progression is push style, from the current year to the next.
Nice property of this solution is that only the last year needs to be stored (i.e, resulting in O(N) memory). It is quite intuitive to implement as the DP progresses through time (years).
Can you explain ur solution a bit more?
@Errichto . Please make more and more dp videos like your previous dp videos including these with complete thought process.Also make series of videos for graphs from beginning to advanced. I completely like your way of teaching. I want more and more videos should be out by you so that I can think like you in every problems.
WOW... theese three DP tutorials you made are so inspiring. I was struggling in algorithm course and the lecturer in my uni don't explain the thinking process. After watching these three tutorials you made, I solved all the DP problems in the assignment
AtCoder Beginner Contests are cool and interesting. And Codeforces is biggest for Competitive Programming in general.
@@Errichto Will be looking into it. Thank you!
Dude great content. Keep at it!
@Errichto it'd be really helpful if you could provide the code for all 3 implementations of this problem.
Thank you so far
next level thinking :)
how many here have attended interviews at FANG (Facebook,Amazon, Netflix,Google)companies and got DP questions in their processes ?
at 7:09 why did u not considered the case for dp[L+1][R]=max(dp[L+1][R],dp[L][R] +p[L]*Y)?
same question
It's crazy to me how similar the fundamental idea of reinforcement learning is to that of dynamic programming.
I’ve tried around 30 DP problems on leetcode and watched tons of lectures on DP as well including yours but I’m still not able to identify what should be the state(here sum) and what should be the parameters(here L,R). As you said you can simply keep what is asked in the question to be the state say maximum value or number of sets. But i have a really hard time deciding what the parameters for a state should be. Even if it obvious sometimes. Also I have difficulty with iterative solutions as you showed in this example we should have L+1 computed so the arrow should be N to 1 which I’m not able to think on my own. What do you suggest I do about it? Is there a resource I can study from to understand what I’m missing better or practice makes perfect?
Thanks. :)
Same here bro, did you figured it out?
hi Errrichto, I was wondering about the top down solution of this problem. So if dp[L][R -1] = dp[L][R] + P[R].Y then dp[L + 1][R] = dp[L][R] + P[L].Y right? So isnt it that I have to implement two separate formula in an iterative method? Like do I need to have 2 separate for loops, 1 for dp[L][R - 1] and 1 for dp[L + 1][R] ? Thanks in advance : D
Awesome video, very helpful stuff! I am struggling with the implementation for the bottom up approach, is there any chance you could show me the full code for this implementation. Thanks! love your videos
in Solution 2, why is dp[L][R-1]=max({dp[L][R]+p[R]*Y, dp[L-1][R-1]+p[L-1]*Y, dp[L][R-1]}) not right?
errichto u r the best.
Is there a systematic way to determine if a problem should be approached with greedy vs DP? Or do you just try to work through the example with greedy, and if it breaks, move on to DP? If the provided example still works for greedy it might be tricky to find a contradiction.
Can you please give me the code for the Solution 2, I don't understand in which order to compute dr[L][R-1]
Approach 3 will be a good solution if the problem is changed to a stream problem where you do not know the size of the array initially, as the solution doesn't depend on the array size.
Approach 1 and 2 are dependent on size of array
this is amazing
@errichto DP lecture 4 when? I am waiting
can you make next video about dp with strings like maximum substring with all distinct characters in a string or minimum length of substring containing all characters in original string. I don't know how to approach these kind of problems one of my colleage said it could be done by dp[N][26] but i would like to know the thinking process.
I get what you're saying. Will keep it in mind.
Found out about you from Joma Tech. During the interview you mentioned that your strong math background helped you skyrocket through Cormen's algorithms book. Specifically what math books in what specific math subjects did you study prior to learning algorithms from the Cormen book? Thanks!
I learned math in school. So, some random Polish school books.
@@Errichto Thanks man! Totally subscibed👍
Do you have any advice on what are the specific math subjects you find important to know prior to hitting the algorithms book?
Isn't R-1 going to be undefined when R=L at the begging of each nested loop?
Sir please post more DP tutorials🙏🙏🙏
Has anyone found where can we practice this problem? I found it at Codechef, but it says "The contest problem is not available for accepting solutions).
Please make more videos on dp. I am weak on it
Nice explanation, I am starting with dp. So as a beginner, I compute the result with the greedy approach. From here how I am supposed to think that the greedy approach will not be the optimal one? Do I first code it out and then think of Dp or just take smaller examples and see from hit and trail that greedy breaks and I should go for dp?
You should think: how would this greedy approach be correct? Can making this decision now hurt me in the future (after a few steps)? If yes, maybe let's try to create a counterexample. It's a bit of intuition plus thinking about proof or counterexample.
Will there be Dynamic Programming Lecture #4?
Thank you!!
when will you make more dp videos ???
Hey Errichto, great tutorial! Do you have the actual code for this exercise? I understood the big picture but im still a bit confused on the actual implementation. Much appreciated.
Can you link the problem on some online judge so that I can submit my solution??
Please tell the sudo code for second and third approach
can you make a video on digit dp also
this might've been asked before, but what do you use to draw by hand? a touchscreen or one of those drawing pads?
Wacom drawing table. Also, you can read FAQ: github.com/Errichto/youtube/wiki/FAQ
12:13 - Solution
Will this series be updated ?
hey i find clrs very tough as its questions are too mathy(atleast for me) any suggestion? should i improve on my math knowledge an stick to clra or find some other book(in this case plz do recommend one)
I don't know your level but if something is very tough, then indeed consider switching to easier source. Use google.
@@Errichto okay thanks.
I love coding but when i dont know a solution to a problem i open editorial or other submissions and learn the algorithm and implement it . Does this help or should try even more to get the solution on my own . Thanks keep up your good work.
Just make sure to try to do it yourself first. Then it's good to check the editorial and learn what is the solution. Read more here: github.com/Errichto/youtube/wiki/How-to-practice%3F
I am not able to implement solution 2
any help.....
have a knock of complicating simple ones
Is the dp series over?
Nice video!
Can you please make videos for some advanced topic you thought to be useful for ICPC....
I make various videos ;p some are useful for icpc, inluding this one (but ofc. it's not that hard)
is it possible to backtrack and print the selling order for the maximum profit ?
Yes. It's a standard technique to remember the best previous state.
@@Errichto thank you for the reply. Is is possible in a future lecture explain how to do this? There's only few content in the internet on this topic.
@@AshikaUmanga Maybe I will do it. Now you can read about it here: codeforces.com/blog/entry/43256 (part about "Recovering the best solution for optimization problems
")
Bro please make some Javascript Programming challenges
keep it up Errichto :)
How can we solve this problem using bottom up approach www.spoj.com/problems/BORW/
I am unable to find its solutin using bottom up anywhere
Can you make a video on tsp, bitmask dp & digit dp. It will be very helpful. Thank you
Even after paying one can not get this type of information.
Discord link is expired
Please make a video on how to compute nCr quickly!
you can easily do it with a concept that :
nCr = (n-1)C(r-1) + (n-1)Cr
and take dimension of dp as dp[n][r] its the best and efficient way to do it
use a for loop with r as min r or n-r
can anybody share the link to the problem?
This problem isn't from any platform/contest.
@@Errichto Should I try this on GeeksForGeeks?
@@sahilsharma2952 I don't understand your question. Try what? Is this problem on GfG?
@@Errichto Yes
@@sahilsharma2952 You are right. www.geeksforgeeks.org/maximum-profit-sale-wines/
sir why not greedy
i personally hate my friends because they never started to code.
great thank u
Number of likes = people who want Errichto to continue this series👇
Sir, do only gifted people (high iq) would succeed in becoming good at programming or normal person like me can do better by practicing it.
What kind of question is this ;p you need some brain capacity to do any job that requires thinking. It doesn't mean you have to be a genius to become a programmer.
@@Errichto kind of impostor syndrome that has been effecting me when I solve programming questions.
can you make a video on digit dp also