🚀 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!
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.
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
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]; } };
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
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.
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.
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.
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
@neetcode Props on the great video! Are palindromic substrings and longest palindromic substrings relevant to DP? If not, why are they in this compilation?
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.
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
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 =)
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
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
Odd or even length strings does not matter static boolean isPallindrom(String str) { boolean isTrue =false; int l=0; int r =str.length()-1; while(r>l) { System.out.println(str); if (str.charAt(l)==str.charAt(r)) { isTrue=true; }; l++; r--; } return isTrue; }
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!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?
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?
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 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?
@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
First of all, a lot of thanks for what you have done, such effort is priceless and let good things happen to you! :) Things I would have done differently: I have just finished watching the first problem, which is Climbing Stairs, and I have to say your approach to explaining it is a bit misleading in its final part. First, you're indexing your array from 0 to 5, but it's dp[0] that contains the number of ways to reach 5. At the same time dp[5] = 1 and that might be confusing because clearly there's more than 1 way to reach 5 from 0 to 5. I do realise that you decided to go backwards but why? Your initial explanation was from 0 to 5. Also, when you show the code, you have no array in there at all. Yes, it's clear that this problem is a plain Fib numbers problem, but for someone who's just started that might be confusing. Anyway, thank you for your effort and don't think of me as someone unthankful - I'm not. I've written all that for those who may struggle trying to understand these things because I've been there multiple times myself.
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
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.
