I'm trying to figure out the followup of the stair problem with limitation on max k jumps. I would think do[I][j] as ith stair with at most j steps, then dp[I][j] = dp[i-2][j-1] + dp[i-1][j-1], and dp[n][k] will be final answer. however, there are a lot of constraints, e.g.: if j > i, dp[i][j] should be same as dp[i][j-1], because it doesn't make any sense if add redundant 1 more step. and code is like: def stair2(n, k): if k == 0: return 0 if k < n/2: return 0 dp = [[0] * (k+1) for i in range(n+1)] for i in range(1, k+1): dp[0][i] = 1 dp[1][i] = 1 dp[0][0] = 1 for i in range(2, n+1): for j in range(1, k+1): if i < j: dp[i][j] = dp[i][j-1] continue dp[i][j] = dp[i-1][j-1] + dp[i-2][j-1] return dp[n][k]
Others : make a 30 minutes video with 10 seconds of usefull stuff, and add a click bait title Errichto : "Consider changing the speed to 1.25". Meanwhile the whole video is priceless
Any of the FANG companies will throw thousands of dollars to have him as an employee. Still, this guy here is making free youtube tutorials for us as well as constantly contributing throughout the community. I just want to know how? Thanks a lot!
Hats off for you Kamil! With every video you succed to teach new things, and to inspire future programmers. I literally can't wait for some new vids from you.
I really appreciate that you're describing the way to approach DP problems. Many other channels just give solutions to specific problems, which does not really help to build the intuition. Your explanation is amazing, thanks!
The efforts you took to add captions show your dedication to articulate your content greatly. Thank you Errichto, this is the best dp tutorial I've come across and I've watched plenty!
Great job! I am so happy to see Polish coders showing up on the world stage strong. After choosing the wrong degree (Civil Engineering) I am now studying programming. This channel will help me with that. Best wishes from Polish living in Tokyo. I really hope to visit my home country on a business trip one day. One of my friend in Gdańsk is already working for a Japanese company so it is a realistic dream ;) Dziękuję za ciężką pracę i twój czas ;)
Yet another amazing video. After watching the video, I was thinking of couple of problems ( modified versions of min path ). Problem 1: Given NxM grid with integer values. Let P be any path from top left corner to bottom right corner. We define F(P) as maximum value along the path P, i.e. F(P) = max{ a[i][j] | (i,j) belonging to P }. Find such path P* such that F(P) has minimum value at P = P*. You can only move down or right. Problem 2: Given NxM grid with integer values. Let P be any path from top left corner to bottom right corner. You can only move down or right. We define F(P) as number of times you changed type of move. More exactly, F(P) = number of points in P such that ( previous point is up and next point is right ) or ( previous point is left and next point is down ). Find such path P* such that F(P) has minimum value at P = P*. EDIT: For problem 2 obviously the answer is F(P) = 2 when you just go all right then all down or vice versa. Let me add, there is also K given. You have to find such path P such that F(P) is atmost K [ F(P)
Thanks Errichto for your channel. It is helping me personally. You are doing one of the best things for all the budding college students and engineers. I hope you continue your effort. Love from India.
The maximum-path sum problem was impossible for me to understand up until 19 minutes and 46 seconds ago. Thank you Errichto!!! If I happen to make it past my coding test on May 11th, I will owe it to this lecture series.
Please make a playlist where you solve leetcode questions. Just record yourself solving the leetcode questions: make one video per question (you solving it and commenting on the problem/solution), put the video into a playlist, and repeat for as many problems as possible. This would attract so many more people to your channel
Hello Errichto, it would be great if you could do a series on recursion and how to think of an approach to write code for recursive problems, it can be useful for solving trees, strings, graphs and dp and a lot more, do consider making vidoes on recursion Thank you for the knowledge
Sir I'm really glad to have come across your videos,earlier I had came across the FFFTTTTT for binary search explanation in textual tutorials but always felt it hard to make sense, thanks for your such crystal clear detailed explanation that brought such clarity. I wish you could make tutorials on matrix exponentiation and how its used for DP . And just one wish that you also make similar video tutorials on Trees and Graphs and with links from where to practice them.I would be really grateful since Im preparing for interviews it would be of great help. Thank you sir..
Lovely methods man! Can you make a lecture series on how you approach different levels of Graph Theory problems? For examples how you solve DFS/BFS based problems, then Djikstra's Algorithm, Topological sorting, min-cut max flow ... and so on? I ask this because a lot of us know this in theory but its very difficult to implement solutions in a competitive coding contest.
if you explains topics like this in such a less time , i don't think i would want to look for any other instructors for all other algo ds topics . Please make videos on all algo ds topics . Your videos will become go to videos in future for everyone. ♥️
Also brought from JomaTech Video, I'm just here because I admire your attitude and willingness to share. I don't plan on making this a career but instead use as a tool to challenge myself to churn solutions to problems. Thank You
Hi Kamil i am a great fan of yours. I watch all your videos and you are my motivation for competitive coding. I wish you all the best for this codejam 2020.
Please next time add some simulation of dp array by creating a box with every medium/hard problems. It will be better to understand for us in less time.
Thank you Errichto! I have known how DP worked, I could apply it, but I didn't really understand it. By that I mean, that some dots haven't connected in my head yet. Like what you have shown here. What is the real reason behind doing it. What if you do it differently. How does the method extend in certain scenarios. You have managed to explain this very simply, for which I thank you sir. :)
Hi Thank you for your amazing lecture and please in other lectures go throught some code forces dynamic programming questions beacuse there is a lot of cllasical dp toturials but i dont think there is a lot about dp in code forces problems.
Sorry if i missunderstood something but i have a question: Always you can solve a dp problem in both (iterative and recursive) or might be problems that is possible only recursively or iterative?
I don't understand the at most k jump what is means? 1: we can come current position from last k position 2: we can make only k or less jumps to reach top
My notes, feel free to iterate if I got something wrong or if there is something that should also be here. Usually, when a recursive/naive solution repeats some form of computation multiple times, it is smarter to save and reuse that computation Most of DP problems belong to one of these 3 types (counting, optimization, confirmation) For counting, think of combinatorics first For optimization and confirmation think of greedy first There are two approaches to dynamic programming: iteration and recursion Iteration is running time is faster, easier to understand the complexity, has shorter code, and more advanced techniques Recursion is easier to apply, could have fewer states, and the order does not matter. Just do the computation and add memoization Most people in competitive programming do the iterative approach because of the faster running times and availability of more advanced techniques [MINE] Dynamic programming appears to trade space for faster running times Implementation of Fibonacci Dynamic programming is not necessary for factorial. Since it has a linear structure. The staircase problem has deep structural similarities to the Fibonacci Minimum path sum problem explanation It is useful to think of all of the relevant information at each position. What do you need to remember at each position? Think about what element would be best to start the array with. In minimum problems, it could be infinity
Wow i spent weeks in high school and uni on this shit and didnt understand absolute shit. And in 20 minutes you just told me everything I didnt know good enough
In the last problem can someone explain to me why wouln't we just consider doing everything backwards greedy? If we are allowed to move only right and down, can't get move from the destination [row][column] to the start but allowed to move LEFT and UP instead using greedy algorithm. Why wouldn't that be a good way?
Consider: 1 1 1 1 1 1 9 2 1 9 1 3 Your algorithm would move from 3 to 1 (left) but then would be forced to pick a 9, whereas a dp solution would correctly pick the 1-1-1-1-2-3 solution. You could I guess also implement a dp solution backwards, kind of like you described, but this is probably harder to implement and therefore unnecessary.
Fibonacci - leetcode.com/problems/fibonacci-number/
Staircase - leetcode.com/problems/climbing-stairs/
Min-Path Grid - leetcode.com/problems/minimum-path-sum/
Count-Paths Grid - leetcode.com/problems/unique-paths/
Thank you for posting the links. It's a great way to understand the content!
I'm trying to figure out the followup of the stair problem with limitation on max k jumps. I would think do[I][j] as ith stair with at most j steps, then dp[I][j] = dp[i-2][j-1] + dp[i-1][j-1], and dp[n][k] will be final answer. however, there are a lot of constraints, e.g.: if j > i, dp[i][j] should be same as dp[i][j-1], because it doesn't make any sense if add redundant 1 more step. and code is like:
def stair2(n, k):
if k == 0:
return 0
if k < n/2:
return 0
dp = [[0] * (k+1) for i in range(n+1)]
for i in range(1, k+1):
dp[0][i] = 1
dp[1][i] = 1
dp[0][0] = 1
for i in range(2, n+1):
for j in range(1, k+1):
if i < j:
dp[i][j] = dp[i][j-1]
continue
dp[i][j] = dp[i-1][j-1] + dp[i-2][j-1]
return dp[n][k]
You're the best
Can u please clarify what is the optimised way to find Fibonacci numbers
Others : make a 30 minutes video with 10 seconds of usefull stuff, and add a click bait title
Errichto : "Consider changing the speed to 1.25". Meanwhile the whole video is priceless
Any of the FANG companies will throw thousands of dollars to have him as an employee. Still, this guy here is making free youtube tutorials for us as well as constantly contributing throughout the community. I just want to know how? Thanks a lot!
because faang and money can go fuck itself
@@nonefvnfvnjnjnjevjenjvonej3384 xDDDDDDD
more like millions...
Because your passion and attitude is more important than millions dollars from FAANG
I think he works at a FAANG
Hats off for you Kamil! With every video you succed to teach new things, and to inspire future programmers. I literally can't wait for some new vids from you.
same here.
Loved your interview with JomaTech!! I am here after that.
praveen s me too
I’m here similarly after one with a google engineer mock interview. The way he explains his thought process is super cool!
:O same
how tf is it possible
I really appreciate that you're describing the way to approach DP problems. Many other channels just give solutions to specific problems, which does not really help to build the intuition. Your explanation is amazing, thanks!
Honestly, you're explanation is way better than the one I was told at the university. Thanks! :)
Very true. Will share this video with my students.
luckily your uni actually taught you this....
Mate, the way you explain dynamic programming is so much better than anything else I've heard from my professors, etc.
The efforts you took to add captions show your dedication to articulate your content greatly. Thank you Errichto, this is the best dp tutorial I've come across and I've watched plenty!
watched this video 1 year ago and still remember how hard it was but you make it easier to think/approach the problem with the good analysis
I did my computer science degree a decade ago. Now i could only wish and dream if i had a teacher like you. Crystal clear N to the point explanation.
The value per minute of these videos is incredible. Thanks so much for putting the time to do this. God Bless You.
Great job! I am so happy to see Polish coders showing up on the world stage strong.
After choosing the wrong degree (Civil Engineering) I am now studying programming. This channel will help me with that.
Best wishes from Polish living in Tokyo. I really hope to visit my home country on a business trip one day. One of my friend in Gdańsk is already working for a Japanese company so it is a realistic dream ;)
Dziękuję za ciężką pracę i twój czas ;)
polish coders are regarded as one of the best in india .
@@bhargavreddy7038 Thank you for sharing it.
Thanks for these videos dude, I learn more on this channel than I learn in a top tier university in CS in US.
Yet another amazing video.
After watching the video, I was thinking of couple of problems ( modified versions of min path ).
Problem 1: Given NxM grid with integer values. Let P be any path from top left corner to bottom right corner. We define F(P) as maximum value along the path P, i.e. F(P) = max{ a[i][j] | (i,j) belonging to P }. Find such path P* such that F(P) has minimum value at P = P*. You can only move down or right.
Problem 2: Given NxM grid with integer values. Let P be any path from top left corner to bottom right corner. You can only move down or right. We define F(P) as number of times you changed type of move. More exactly, F(P) = number of points in P such that ( previous point is up and next point is right ) or ( previous point is left and next point is down ). Find such path P* such that F(P) has minimum value at P = P*.
EDIT: For problem 2 obviously the answer is F(P) = 2 when you just go all right then all down or vice versa. Let me add, there is also K given. You have to find such path P such that F(P) is atmost K [ F(P)
@Errichto Congratulations on 10k subscribers. Really awesome milestone. Also, I think you missed my question. Can you please share your ideas?
this is the best explanation of DP under 20 mins covering popular topics 👏👏👏👏 Thank you
@Errichto 13:28 subtitle should be : And every state you compute in constant time, dp[i][k] = dp[i-1][k-1] + dp[i-2][k-1] + .. dp[i-k][k-1]
Thanks Errichto for your channel. It is helping me personally. You are doing one of the best things for all the budding college students and engineers.
I hope you continue your effort. Love from India.
No one else made me understand DP until you came along
:)
Errichto thanks for putting this up. This is as precise as it can get.
The maximum-path sum problem was impossible for me to understand up until 19 minutes and 46 seconds ago. Thank you Errichto!!! If I happen to make it past my coding test on May 11th, I will owe it to this lecture series.
I come from the Joma channel, you're really incredible, I'm new in this world, and I hope to learn a lot from your channel.
Best tutorial about dp so far .Thanks.
pure gold. looking forward for next video
Seriously quality of information is very good
Thank you, your videos are purely based on content quality and that's the best part.
Please make a playlist where you solve leetcode questions. Just record yourself solving the leetcode questions: make one video per question (you solving it and commenting on the problem/solution), put the video into a playlist, and repeat for as many problems as possible. This would attract so many more people to your channel
Great video Kamil. I particularly enjoyed your explanation about dimensions of the state and transitions. Thank you very much!
hey errichto! These videos are awesome and best
Great Insights on how to approach dp problems. I request for more dp content as it is hard to get comfortable with.
Thank you so much for this man, I've never been able to perceive recursion
Hello Errichto, it would be great if you could do a series on recursion and how to think of an approach to write code for recursive problems, it can be useful for solving trees, strings, graphs and dp and a lot more, do consider making vidoes on recursion
Thank you for the knowledge
Very precise and clear Explanation Kamil!!
Sir I'm really glad to have come across your videos,earlier I had came across the FFFTTTTT for binary search explanation in textual tutorials but always felt it hard to make sense, thanks for your such crystal clear detailed explanation that brought such clarity.
I wish you could make tutorials on matrix exponentiation and how its used for DP .
And just one wish that you also make similar video tutorials on Trees and Graphs and with links from where to practice them.I would be really grateful since Im preparing for interviews it would be of great help. Thank you sir..
Thank you for the video. It helped a lot to know how to think to reach a solution for DP
Lovely methods man! Can you make a lecture series on how you approach different levels of Graph Theory problems? For examples how you solve DFS/BFS based problems, then Djikstra's Algorithm, Topological sorting, min-cut max flow ... and so on? I ask this because a lot of us know this in theory but its very difficult to implement solutions in a competitive coding contest.
This video is Gold For understanding the dp working.... LOVE YOU BRO FROM INDIA....
This is an incredible learning resource, thank you!
Thanks for dp lec😀, please upload more such tutorial.
if you explains topics like this in such a less time , i don't think i would want to look for any other instructors for all other algo ds topics . Please make videos on all algo ds topics . Your videos will become go to videos in future for everyone. ♥️
Thanks!
Thank you kamil! Please make a video on Graph Algorithms as well. Really appreciate it.
Very nice video sir. There is always something to learn from your every video.
Also brought from JomaTech Video, I'm just here because I admire your attitude and willingness to share. I don't plan on making this a career but instead use as a tool to challenge myself to churn solutions to problems. Thank You
@errichto: in the last minimum path sum, shouldn't we take the minimum of the previous of the two values (left and top) instead of the maximum?
Yep, you are right. I corrected it in captions but the video will stay with this mistake forever :D thanks for noticing!
@Tyler Durden How? In UA-cam editor, I only see an option to add blur.
@@Errichto or you can pin this comment chain to the top
@@Errichto I think it is possible, since in this video, you already corrected one mistake, where you put "*Space" word in the video
Wow! This video has made dp much easier for me. I find this extremely helpful. Thanks to you!
I was really struggling with dp and your videos helped me allot . Thanks
Thank you so much Errichto, your explaining style really helped me a lot.
We need more dp lectures which is needed to competitive programming.
thanks... a lot for such video lectures it really helps a lot eagerly waiting for next dp lecture with some interesting problem
Thanks for the video, I was facing problems while learning dp ,I saw half of the video and was able to solve all the four problems.
finally someone made dp looks simple.. this will help me alot thx
Dimension of dp is the number of variables which can completely define a state
Thanks for this awesome video. I was able to solve all four problems. Previously I got the min-path problem in an interview.
Thank you just made the DP really easy to understand when and how to use
Great video! Hope you make many more of these.
high quality content as always errichto
Dynamic programming Lecture #0 :
Intro : 0:05
When do we use DP ? : 0:45
Iteration vs Recursion : 1:44
Fibonacci Series : 3:39
Factorial : 7:36
Stairs : 8:33
Minimum Path Sum : 14:04
Summary : 18:01
Huge RESPECT to u Sir!!!!
Please dnt stop and keep doing the good work....
Hi Kamil i am a great fan of yours. I watch all your videos and you are my motivation for competitive coding. I wish you all the best for this codejam 2020.
Clear explanations and nice graphs, thanks!
Please next time add some simulation of dp array by creating a box with every medium/hard problems. It will be better to understand for us in less time.
Thank you Errichto! I have known how DP worked, I could apply it, but I didn't really understand it. By that I mean, that some dots haven't connected in my head yet. Like what you have shown here. What is the real reason behind doing it. What if you do it differently. How does the method extend in certain scenarios. You have managed to explain this very simply, for which I thank you sir. :)
first time I saw you talk so much
great explaination sir errichto
Great video. Didn’t need subtitles as what you said is clear.
This is what I've been looking for
Genius, you have best explanation with straigh to the point
Hi Thank you for your amazing lecture and please in other lectures go throught some code forces dynamic programming questions beacuse there is a lot of cllasical dp toturials but i dont think there is a lot about dp in code forces problems.
Absolutely Gold...about solving dp problem
Fantastic as always tbh. How many problems do you think you're going to go over?
I have no idea, to be honest.
Great video on dp! Hoping to see many more videos about competitive programming
dp is used to save time which gets wasted into doing repeated work
Generally this happens when one state depends on more than one state
Now I understand!:
- I watched this 3x
- did the problems you linked
This content is gold ! Thank you !
Sorry if i missunderstood something but i have a question:
Always you can solve a dp problem in both (iterative and recursive) or might be problems that is possible only recursively or iterative?
Lucas Guerrero Any recursive problem can be solved iteratively.
Amazing channel !. Would love to see some Discrete Math and Graph Theory :)
Please create a series on graphs and graphing algorithms
Really, thank you so much, it does help a lot.
I wish you provide the algorithms too
really good!! Add playlist for other topics also
awesome video sir , learned a lot...
You lectures are amazing
Please go through atcoder knapsack problems(both variations) and make a video on them
Best explanation ever.
Fantastic series. Thank you.
Sir please make more videos on Dynamic Programming.
I don't understand the at most k jump what is means?
1: we can come current position from last k position
2: we can make only k or less jumps to reach top
Second one
My notes, feel free to iterate if I got something wrong or if there is something that should also be here.
Usually, when a recursive/naive solution repeats some form of computation multiple times, it is smarter to save and reuse that computation
Most of DP problems belong to one of these 3 types (counting, optimization, confirmation)
For counting, think of combinatorics first
For optimization and confirmation think of greedy first
There are two approaches to dynamic programming: iteration and recursion
Iteration is running time is faster, easier to understand the complexity, has shorter code, and more advanced techniques
Recursion is easier to apply, could have fewer states, and the order does not matter. Just do the computation and add memoization
Most people in competitive programming do the iterative approach because of the faster running times and availability of more advanced techniques
[MINE] Dynamic programming appears to trade space for faster running times
Implementation of Fibonacci
Dynamic programming is not necessary for factorial. Since it has a linear structure.
The staircase problem has deep structural similarities to the Fibonacci
Minimum path sum problem explanation
It is useful to think of all of the relevant information at each position. What do you need to remember at each position?
Think about what element would be best to start the array with. In minimum problems, it could be infinity
Don't forget : What is important so far ?
ok i'm at a certain position now what do next? pls help me with this. i'm lost here
I'm convinced Errichto was sent by God
Wow i spent weeks in high school and uni on this shit and didnt understand absolute shit. And in 20 minutes you just told me everything I didnt know good enough
Thank you for sharing this. It is really helpful.
Best DP video ever. Thanks.
Great video! Maybe consider add code snippet to make the video more clear
Amazing just amazing
Thanks for sharing awesome DP tutorial.
Thank you Kamil, you are the best!!
0:5:46 imho should be N+1 to include the last index as well
Thank you, Errichto!!!
I am a big fan of you from Bangladesh.please upload some video on graph theory.
In the last problem can someone explain to me why wouln't we just consider doing everything backwards greedy?
If we are allowed to move only right and down, can't get move from the destination [row][column] to the start but allowed to move LEFT and UP instead using greedy algorithm. Why wouldn't that be a good way?
Consider:
1 1 1 1
1 1 9 2
1 9 1 3
Your algorithm would move from 3 to 1 (left) but then would be forced to pick a 9, whereas a dp solution would correctly pick the 1-1-1-1-2-3 solution. You could I guess also implement a dp solution backwards, kind of like you described, but this is probably harder to implement and therefore unnecessary.
The minimum sum path can also be achieved by doing a BFS ?