Video nenà dostupné.
OmlouvĂĄme se.
Dynamic Programming 1D - Full Course - Python
VloĆŸit
- Äas pĆidĂĄn 6. 08. 2024
- đ neetcode.io/ - A better way to prepare for Coding Interviews
Checkout my second Channel: @NeetCodeIO
đ„· Discord: / discord
đŠ Twitter: / neetcode1
â BLIND-75 PLAYLIST: âą Two Sum - Leetcode 1 -...
đĄ DYNAMIC PROGRAMMING PLAYLIST: âą House Robber - Leetco...
0:00 - Intro
1:05 - Climbing Stairs
19:03 - Min Cost Climbing Stairs
38:16 - House Robber
48:45 - House Robber II
58:58 - Longest Palindromic Substring
1:07:00 - Palindromic Substrings
1:21:51 - Decode Ways
1:37:08 - Coin Change
1:56:23 - Maximum Product Subarray
2:11:46 - Word Break
2:27:06 - Longest Increasing Subsequence
2:45:20 - Partition Equal Subset Sum
#neetcode #leetcode #python
đ neetcode.io - Get access to every current and future course I ever create.
Spreadsheet from the video: docs.google.com/spreadsheets/d/1A2PaQKcdwO_lwxz9bAnxXnIQayCouZP6d-ENrBz_NXc/edit?usp=sharing
Hi Mr NeetCode dude, I just wanted to ask, do you have tier pricing that changes based on the country? For example, there are developing countries in Africa that generally tend to have a lower pricing since the $ is extremely high to the ZAR - South African Rand. There are other countries as well that would struggle. Do you intend on having a way to assist us too? I'm asking because you're having a launch sale and perhaps by the time you even get a chance to consider different tier pricing based on different countries it may be too late :( Do know however, I'm extremely grateful for the existence of NeetCode and everything that you've done!
Dear Neetcode, Could you please publish a video full course on graph theory
I'd like to share a few points. With DP, one of the main challenge is how do you recognize a problem is indeed a DP problem. It can be misleading at times that a given problem is indeed a DP problem.
Therefore, I'd say that this course and more upcoming DP parts that you might be posting, would be great if you start each question with pure analysis of why this problem is a DP problem to begin with. Taking a view on the question as if it has never been seen and then you apply contain ideas to identify if its a DP problem or not.
The reason I'm bringing this point is because it just so happened that one of my friend shared his experience with me that he had a few years ago where during interview, he thought the problem is a DP and after 25 mins in the interview, he realized that's its not but he had waisted essentially all the critical time.
Long story short, would be great that for every question, would be great to talk about what attributes of such problem made it obvious that its a DP problem.
Facts. for me personally almost every question i do im always trying to look for a dp solution but i dont really know if it is a dp problem
I get your point and I agree but I believe it's one of those things that you have to build an intuition for, in other words, it comes with practice.
In an algorithms class one first learns about greedy algorithms, then memoization before moving into DP. I think this helps build an intuition. So anyone looking to gain intuition about when DP is applicable may benefit from reading up on those concepts first, especially memoization.
That said, the first example of the fibonacci sequence is a good start. Think of times where work has to be repeated because future calculations require the work of previous steps, as in the fibonacci sequence. With memoization, instead of re-calculating every step, we can save the results at each step and recall the solution in future function calls to speed up the time needed.
Take this as how to recognise the problem is a DP:
1. With pen & paper, do the problem have sub-problems?
2. Does the sub-problems return similar value or in a pattern that will be used for next iteration(sub-problem)?
If it is, then try to solve this way:
1. you can follow tabulation(array to store data) or memoisation(hashSet or hashMap).
2. Sometimes the problem may not ask for the dp array or dp hash, then you may use two variables(think these as pointers that may need to update at each iteration). At the end return the value.
Good question, another one that I have is how do we come to understand that there is a binary algorithm at place? Either we take the current value or we do not? It would appear that we could just loop through all possible options (except the current one), which would still work, but be slower and get a TLE on leetcode
You're doing amazing work for all who wants to be good at algorithms and pass interviews. Mad respect!
Thanks a lot brother. May God bless you abundantly
Most loving CZcams commenter
This is amazing, thanks for all the work you do.
Ohhh neetcode only if I could express how much I owe you for improving my problem solving skills
great stuff! hope for other topics covered the same way!
The best timing. Ä° was in need of this. Thank you so much Sir.
This is what I'm looking for! Thank you!
I've been watching your videos so much through my interview preparations that your voice sounds like a mother's lullaby to me at this point.
Thank you very much for this video. I finally solved my very own medium dp lc after watching a quarter of your video. I'm gonna finish this and hopefully, I can stand on my own feet after.
Thanks a lot, We need more such full course vedios on each module, It really helps
I agree, climbing stairs was indeed explained top notch.
I really appreciate your work, your explanation really works
Dude this is amazing material! Thank you so much for the education and your teachings! When I get a job, Ima have to take you out for lunch! Truly appreciate your work buddy =)
Absolutely love your content. Itâs so neet and easy to follow for the layman. Do you have a Rumble channel as well?
Oh my man this was so needed thankyou so much sir â€ïž
I Really appreciate these efforts you are taking manđ„
Thanks neetcode eagerly waited for this, Hope u will upload this type of content more.
Oh my God ! Can't thank you enough. Thank you so much for this
Watching this in the weekend. I can't be happier
Absolute legend for this!
Waiting for this ,best explaination ever đ„đ„
I love this, Thank you! Can you do the same for dfs and bfs algorithms?
Amazing!! Waiting for 2D DP :)
I'm not sure who needs this, but I guess we can use the similar format for all 1D problems-
class Solution {
public:
int solve(vector& ways, int n, int start){
if(start >= n){
// no way to reach the end
return 0;
}
if(ways[start] != -1){
// already calculated
return ways[start];
}
// not cal
// need to cal
// it always depends on the next problem
return ways[start] = solve(ways, n, start + 1) + solve(ways, n, start + 2);
}
int climbStairs(int n) {
// using the concept of DP
vector ways(n + 1, -1);
if(n < 2){
return 1;
}
ways[n] = 0;
ways[n-1] = 1;
ways[n-2] = 2;
// ways means number of ways we can reach the end
// if the start position is i
solve(ways, n, 0);
return ways[0];
}
};
So incredible you could put in tonnes of hours into quality work. Thanks for creating this amazing resource.
Great stuff... Learnt a lot sir
You did it finaly, God Damn, you have no idea what great help you just did, damn bruh you are God sent
this video helped me a lot. Thanks
You. Are. Absolutely. Amazing!!!!
MY MAN IS BACK
Wow, this is amazing tutorial, DP in many case (n*2) -1 or ( n- n,pow(2)) đ, great work
Dear Neetcode, thank you for uploading this. I have been following your content for quite some time and I really appreciate the effort you have put into creating content for DSA. However, I would really appreciate it if you could highlight the core in-depth reason for why such DP patterns exist, and how to identify them. So a template, instead of solutions.
DP is used when you have n ways to do something. Here that n is the number of steps you can take. The question can be changed to say you can can take 1 or 2 or 3 steps. Now if you give 20 stairs, you have 3 ways to get there. As you can see there is no straight forward answer. This is where DP comes in the picture. DP allows you to break the problem down into a very very small sub problem. Once you solve small sub problem then next problem builds on top of it.
So instead of solving to 20 steps, solve it for smaller number. What's the smallest number you can solve it for???? 0. Also in dp questions where we have to count n ways, I find it much better approach to go backwards. Instead of finding ways to get to 20, find ways to get to 0.
for 3 steps where you are allowed to take 1or 2 steps, it'd look like
3
2/ \1
1 2
2/ \1 2/ \ 1
-1 0 0 1
2 / \1
-1 0
Anytime you see 0, you have a positive case meaning that path will yield correct result. If value goes < 0, it means it won't work. So the code will look like
public int GetCount(int totalSteps) {
if(totalSteps == 0) return 1;
if(totalSteps < 0) return 0;
return GetCount(totalSteps-2) + GetCount(totalSteps-1);
}
Then you add memoization to optimize the time but you get the idea.
Its an amazing concept but once you get a hang of it, you'd feel most satisfied solving these questions.
@@sherazdotnet you're awesome
@@sherazdotnet thanks bro
Thanks!Could you do live dynamic programming session , so we can learn from your thought process?Btw( for 02:45:45 ) if the input array is [1,4,11,5} dont [1,4] and [5] is even subsets,even if they are not equal to half of sum of the array?
Bro, this is gold.
Thank you neetcode đ
@neetcode Props on the great video! Are palindromic substrings and longest palindromic substrings relevant to DP? If not, why are they in this compilation?
Climbing Stairs can be written in just three lines(instead of five), in python for swapping two variables you don't need a Temp variable, you can use
a, b = b, a or ( one, two = one + two, one )
class Solution:
def climbStairs(self, n: int) -> int:
one, two = 1, 1
for i in range(n-1):
one, two = one + two, one
return one
For anyone reading this, reason this works is because in python the expressions on the right side of the = sign are evaluated first, therefore one + two and one are calculated based on original values of one and two. Then it assigns the results to one and two on the left side
the two variable approach to solving the decode ways is missing in this video, but really helpful video. Thanks a lot.
Neetcode is the Hero we dont deserve but the hero we needed. He is the Dark Knight of LeetCode.
great content
Love you Neetcode â€
Hello everyone!
I have a question regarding the problem 300 "Longest increasing subsequence". Why didn't we write:
LIS = [1] * (len(nums)+1) instead of LIS = [1] * len(nums)
For example, in the previous problem "Word Break" we've used the +1. In which cases do we use the +1 when we define dp and in which cases we do not?
Thank you
In the climbing stairs problem, why is the value for the base case 1? If we are at the base case, then there are 0 ways to reach the base case rightâŠ.? I realise if we initialise the base case to zero then the code wonât work. I just want to understand what other reason there is for the base case to be one.
The original problem is about routes - how many routes can you take.
from 5 to 5 you can take 1 route
from 2 to 5 you can take the route that will lead you to 3, or the route that will lead you to 4
Well done brođđđđđđ
For the first 1D example, why does the fib sequence start from 1 and not 0?
Love you man you are the best
Very helpfull course, Highly recommended
I paid for the lifetime membership yesterday, but this super long and helpful video is just for free.
So, goodbye my money, I have to support this cool guy indeed.
that's a great pic of Son Ye-jin!
Well, this does not include the 20 mins 1D DP course in his pro member content. Your money is still worth it.
Amazing đđŒ
Thanks a lot!
For problem "decode ways" Doesn't initializing dp[len(s] = 1 mean that null string can be decoded in 1 way? I understand how this works in code but conceptually I don't see how a null string can be decoded
you are god for me and thanks for these dp course in pythonđđ
For the last problem, can someone explain why the time complexity is not 2^n? If all the sum is unique, then the size of set should double each time, thus it's 2^n. Why doesn't this happen?
Thanks neetcode
thank you for the contribution for the human kind.
Thanks!
Youâre doing godâs work
Dear Neetcode, Could you please publish a video full course on graph theory
That infinite loop while trying to add to the same set you are iterating through was confusing me. Thanks!
Is this video a combination of all the previous videos cut together? or is it recut/edited to string together experiences drawn from previous questions?
Nice video...can u please do a video about sliding window technique
Thank youđ«
Here is my solution using Recursion + Memoization. Code is written in c#
public int CountSteps(int totalSteps, Dictionary memo) {
if(totalSteps ==0) {
return 1;
}
if(totalSteps < 0) {
return 0;
}
if(memo.ContainsKey(totalSteps)) {
return memo[totalSteps];
}
var usingOneStep = CountSteps(totalSteps-1, memo);
var usingTwoSteps = CountSteps(totalSteps-2, memo);
memo[totalSteps] = usingOneStep + usingTwoSteps;
return memo[totalSteps];
}
Thanks man. Respect from đźđł
When I see your video I realize the next 3 hours are gonna be coool
Thanks Guru. You are my Dronacharya
2:08:59 why is the third value in the min necessary (just n). cur_max can never be less than 1. If cur_max is 1, its the same as n, if its larger, it's bigger than n.
Hi
Your whiteboard is amazing. Which tool do you use for whiteboarding
13:20, at the last step 5, how many ways to land on the same step land on itself, why 1?
How is longest palindromic substring dynamic programming?
I have a question for Maximun Product Subarray. What if the array is just [0], your code will output 1 as u set curMax as 1 by default. However, the ans should be 0 right? Maybe I should deal with this case especially?
Can't believe he is an Indian đ«Ąđ
im confused by what i see and what i hear.
you say the for loop will run until it reaches the beginning of the array. but whats written is -3, -1, -1
so to my understand, it starts at index -3, then goes back -1 index every iteration, until it reaches the last index -1??
that makes no sense to me
Goat
thanks for teaching me how to rob a neighborhood efficiently
@NeeCode in house robber 2 problem(problem number 213) if the robber starts stealing from house somewhere in middle . is it not separate case we have to consider . so I think for each number in array we have to skip it and execute the helper function
Hey Neetcode, What app and tool you use for teaching?
Can we improve the efficiency at 2:24:28 by mutating wordDict into the form where the key is len(word) and the value is a list of all words of that length (no extra space). Then we can check:
for key in wordDict:
if i+key in dp and dp[i + key] = True:
for word in wordDict[key]:
#check the word
That way, you eliminate the vast majority of building dp.
For the first problem, why is it that we put 1 in 5. If we are already if 5 and we can either go up by. 1 or 2 then shouldn't the possible step be 0?(As we are already in the solution). Can someone clarify pls
I have the same question
+1, because by this logic we should place 2 in 4
@ 18:53 the code doesn't run well for a higher value of n. I tried with a value of 500,000. It hung.
In DP for the 5th a stair, why is the value 5 and not 0?
how is the palindrome question related to dynamic programming? (Great vids, btw!)
Really Awesome work .
Thank you so much Bro
please make a video on recursion and backtracking also
I didn't quite get it for the house robber 1 problem after watching 2 times. Maybe I failed in one key thought jump.
really learning dp from a google employer is a god grace
Whatâs the difference between this and recursion
Hey Neetcode
Brute Forced a super inefficient piece of code :P :
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
length = len(s)
for w in wordDict:
if length==0:
return True
while length>=0 and len(w)
Iâm so confused. The maps generated in the problems all seem to have unique rules that arent clear to me. Feels like I missed a reading assignment maybe or lecture.
The longest subsequence problem was troubling for me. ace. abcde. The matrix and comparisons sounded so natural but seemed convoluted to me. Why is this more efficient than sequence analyzer? Like the subsequence ace is visible in abcde without needing a map. (Granted I donât know if that means there is a solution that can be computed more easily)
These are great I just feel like an idiot cause I feel like Iâm doing physics but didnât learn the kinematic equations or something similar.
Legend is back đ„đ„đ„
Why is Longest Palindromic Substring considered DP??
love you dude....
if God is there... God bless you
can u make it to run in console?
How long will the 25 percent sale last?
your voice is very appealing.
my dear god plz do more dp thanks!
Recursion with Linked List combined please....