House Robber - Leetcode 198 - Python Dynamic Programming
Vložit
- čas přidán 5. 07. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
Twitter: / neetcode1
Discord: / discord
💡 CODING SOLUTIONS: • Coding Interview Solut...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
🌲 TREE PLAYLIST: • Invert Binary Tree - D...
💡 GRAPH PLAYLIST: • Course Schedule - Grap...
💡 BACKTRACKING PLAYLIST: • Word Search - Backtrac...
💡 LINKED LIST PLAYLIST: • Reverse Linked List - ...
Problem Link: neetcode.io/problems/house-ro...
0:00 Conceptual
8:03 Coding optimal solution
#python #neetcode #leetcode
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission. - Věda a technologie
🚀 neetcode.io/ - A better way to prepare for Coding Interviews
Good playlist 👍
I solved this problem in n^2 time complexity and leetcode gave me 100% beat, i thought it was the only solution (finding the max from i+2 to n) and when i open youtube it gave me this video as recommendation.😂😂😂😂
I robbed my entire neighborhood thanks to this video.
Posting this from jail though
sorry but told you to optimize first
You didn't optimize property bro
Wow, can’t believe you robbed from two adjacent houses
Thanks to leetcode i've given up working as a software engineer, I am now a professional house robber.
This video really helped a lot! Thanks to you, I've gotten away with multiple house robberies.
💀
Had us in the first half, not gonna lie
🤣🤣🤣🤣
😂😂😂😂
I like how they upgraded this to medium haha
😂😂
Thanks!
I submitted correct code on leetcode just by watching conceptual part and without even seeing the coding part and later when I checked my code was almost identical to what you wrote. Excellent explanation. You are doing a really great work here
what was your solution if you don't mind me asking?
class Solution {
public:
int rob(vector& nums) {
int n = nums.size();
vector dp (n, 0);
dp[0] = nums[0];
for (int i = 1; i < n; i++) {
dp[i] = max(dp[i - 1], nums[i]);
if (i > 1) dp[i] = max(dp[i], nums[i] + dp[i - 2]);
}
return dp[n - 1];
}
};@@sonicspider49
you inspired me bro.
The video section until 5:05 seems to show one way to solve this, while 5:05-on shows a similar, but actual way the code you wrote solves it.
When viewing the first time, it seems puzzling why you seem to go back to solving it from scratch, after getting important insights. While the 5:05 section explains why this will be the maximum, there's some gap and the two sections seem to be somewhat parallel in first view.
It would have helped to tie them together better.
The recurrence relationship of dynamic programming is based on "previous" optimal substructure.
Instead of defining it:
rob[n] = max( arr[n] + rob[2:n], rob[1:n] ) @4:40
It should be:
rob[n] = max( arr[n] + rob[n-2], rob[n-1] ).
Hope this helps people who came across this post.
This is helpful. DP is so difficult for me; I've watched the Free Code Camp video on it and practiced dozens of problems, but I just have some sort of mental block when it comes to this topic. Thank you for the video!
you are not alone!! xD
Look up 'mental block' in the dictionary, you'll find my face next to it.
same!!
Wow me too! TT^TT im not alone on this DP mental block
@@kimberlygovea8591 did you get better?
For people confused this is a space optimised dp solution. Similar to solving fibonacci iteratively. If you compare to solving fiboannci with a memo table, it will be more similar and more intuitive to further dp problems.
you should explain that we return rob2 because rob2 is actually temp right now, which is essentially the max we can get for the last house.
Thanks for listening, and adding a dp question! Though I had solved this before, learnt a ton from this one! Thank you @NeetCode.
Bottom-up approach:
class Solution:
def rob(self, nums: List[int]) -> int:
nums.append(0)
for i in range(len(nums) - 3, -1, -1):
nums[i] = max(nums[i] + nums[i + 2], nums[i + 1])
return max(nums[0], nums[1])
That’s how I did it. I thought it was pretty optimized. But the way Neet did it has an O(1) space complexity
Thanks for the explanation. Here is an alternative solution that can be easier to understand :
def rob(self, nums: List[int]) -> int:
if not nums :
return 0
if len(nums) == 1:
return nums[0]
dp = [0] * len(nums)
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2,len(nums)):
dp[i] = max(dp[i-1],nums[i]+dp[i-2])
return dp[-1]
your logic is so insane man, every approach you come up with my jaw drop and its really impressive how you think, it might seem exaggerating but as a newbie coder who gets stuck frequently, it is impressive what you do
I love how you explain the problem with calm and clear english. Thank you very much, I didn't think I would understand how to solve this problem. But after watching your video I feel like dynamic programming is easier than I thought. Thanks a lot man.
Good to know there's an actual algorithm for robbing houses!
Thanks! Leetcode changed this problem to medium difficulty 😃
What about making each week a video about the leetcode weekly contest hard question? I always have problems to solve this and maybe there is a niche for it, because nobody else does a clear video solution about this!
Your explanation is the clearest explanation that I had ever found! thank you so much!
Thank you bro, your video really helped me understand how i should approach dynamic programming problems. Thank you so much again!!!
Every single time I look for any solution, I try to search your channel first that, have you uploaded its solution. Thanks for amazing solutions ♥
Such great explanation! Thanks mate and keep going
I was struggling with understanding solutions in the forum, this really helped clarify how recurrence relation is working here
Best man on the earth, clear and crisp solutions. Thankyou so much.🙌🙌👌
Amazing. I tried memoization which also worked. But your solution's conciseness is simply wow
Same. But I'm struggling to edit the recursive solution for House Robber 2
Nice Explanation!
From your conceptual explanation I came up with this solution.
class Solution:
def rob(self, nums: List[int]) -> int:
length = len(nums)
if length
Maybe it's just me but I think it is way more understandable without auxiliary variables and implement a bottom-up DP solution. It helped me to store the max amount of robbed in a int[] dp array and initialize array to have [nums[0], max(nums[0], nums[1]).... and then iterating through the nums array.
you can even use the nums argument directly.
LeetCode updated problem 198 difficulty to Medium.
Should this video be moved from Easy playlist to Medium also?
It's kind both, isn't it?
With DP intuition, it becomes relatively easy (after watching your explanation).
Simple clean explanation 🔥🔥... great job man....
we can also work this backward from N-1 to 0-th index :D. denote DP[n] as the robbed amount if we start from the n-th house (including the n-th), denote DPN[n] as robbed amount if we start from at least n+1-th house (not including n-th). DP[n] = nums[n] + max(DP[n + 2], DPN[n + 2]). DPN[n] = max(DP[n + 1], DPN[n + 1]). we initialise DP[N-1] = nums[N -1], DPN[N-1] = 0 and also the N -2 ones .
That was cool - doing it in O(1) space.
Awesome explanation! Thank you so much!
I understand what you did, but I still don't understand how I can come up with the same solution.
Definitely need more practice.
little correction, check for input [2,1,1,2]
// Assuming all +ve values
var rob = function(nums) {
if(!nums) return 0;
if(nums.length == 1 ) return nums[0];
if(nums.length == 2) return Math.max(nums[1], nums[0]);
let rob1 = nums[0];
let rob2 = Math.max(nums[0], nums[1]);
for (let i=2; i< nums.length; i++) {
// Here we are
let temp = Math.max(rob1 + nums[i], rob2);
rob1 = rob2;
rob2 = temp;
}
return rob2;
};
Great solution and explanation: quite easy to grasp, but how is it related to the dynamic programming approach?
This is DP coded in bottom-up approach. If top-down, then it will be using recursion
You are a great human being. Thanks.
can't believe you are writing with a mouse .... Appreciate your efforts dude... Awesome explanation by the way
The solution, video, and explanation are beautiful.
Thanks 😊
Hello, how can we rob in house 0 &1 and ignore 3 at index 4 ? Robbing in house 0&1 means that we rob in adjacent houses right ?
After learning a lot of dynamic programming problems from you.... Today I was able to solve this by myself.
The part that makes sense is choosing the first or not and defining that in terms of recursion: `max(rob(nums[1:]), nums[0] + rob(nums[2:]))` -- But the switch from a recursive approach to this rolling array is confusing. Memoization can also be done with a dictionary -- it's O(n) instead of O(1), but for whatever reason it makes more sense to me...
The way he naming variable maybe be confusing;
in my op: the current max Rob depends on prev rob and the 2 prev
Since the current rob depends on 2 previous rob; we only need to keep track of them only; not the entire map. And this called improved DP.
so it could be
loop through the array:
#find current max
-curr = max (n + 2prev, prev) #n + 2prev cuz of parallel constraint.
#move the prev and 2prev up 1.
-prev2 = prev
-prev = curr
finally return prev which is the curr.
You can also use something similar to this to solve fibonacci, which doesn't need to store the entire map.
class Solution:
def rob(self, nums: List[int]) -> int:
rob1, rob2 = 0, 0
for n in nums:
rob1, rob2 = rob2, max(n + rob1, rob2)
return rob2
You don't need the temp variable, you can just swap on the same line.
this makes more sense, thanks !
The confusing part for me was/is to understand why we need to calculate max. I think with a larger input array it could be clearer. The answer I came up with to my own question it's because the current element will become (after we move forward two times) the element that we want to check how much we could rob when we where there.
Max is a built in function to get max value from two inputs
I solved it with Recursion but this solution is smart! Thank You.
i did some of the previous DP questions on the blind 75 with your videos and figured this out using bottom up approach, but my solution ended up being O(n^2) time, while this solution is just O(n). ugh...how can you tell which to use? also looking in the comments i see a O(n) bottom up solution...
Is this solution also work for if there is negative values?
At about 5:15, its mentioned that doing computations from the end of the array can be confusing - even I tried doing that and got it incorrect multiple times. How do you guys determine in such problems whether to start from the front or from the back? I did Min Cost Climbing Stairs just before this problem and therein I noticed that it was simpler to do the computation from the end. I'm in quite some dilemma!
Got it using the other end of the array - Memoized solution :-
class Solution {
public int robAmount(int[] nums, int[] dp, int n) {
if (n < 0)
return 0;
if (dp[n] != -1)
return dp[n];
dp[n] = Math.max(nums[n] + robAmount(nums, dp, n - 2), robAmount(nums, dp, n - 1));
return dp[n];
}
public int rob(int[] nums) {
int n = nums.length, dp[] = new int[n];
Arrays.fill(dp, -1);
return robAmount(nums, dp, n - 1);
}
}
This is amazing, how could you come up with this ideal
I have a question. What if we skip 2 houses from the 1st house, and than either 1 or 2 houses and so on? Why this route wouldn't bring us to a more yield?
Wow I wish I saw this video before my Cisco assessment, I got a question exactly like this except the story was that you couldn’t pick two chocolates from adjacent candy jars
This is one of the most underrated problems. Most people would be able to solve it, but would have a very superficial understanding of the why the solution works. This video illustrates very carefully as to WHY certain decisions were made while coming up with the solution eg. why don't you need a full dp array, why 2 variables suffice, why do you have to do rob1+n....it's an easy problem but the thinking that goes in is amazing. You really need to have a clear mind to explain it. Solving it is easy, explaining the solution is difficult.
Found one problem in explanation 4:30 time rob = max(arr[0] + rob[2:n], rob1) actually you can't go to [2:n] but [2:n-2], [1:n-1] as you picked the arr[0] from the example. This problem you coded is basically optimization for dynamic arr problem. I found dp array problem easier to understand.
It took me a while to get it... Interesting logic.
I am dumb, I don't get your explanation at all and it seems I'm the only one, looking at the comments.
you're not the only one!
Pretty happy I was able to come up with the solution for this one, including using memoization and submitting on Leetcode, in like 15 min.
Came here to see if my solution was actually optimal. Feeling a lot closer to being ready for my interviews and these videos are definitely helping.
If I may, from what I have understand of DP so far is that you iteratively save your result in an array/table. So I suppose that your solution at 7:02 is DP and I managed to understand it and implement a solution. However when you only use you variables rob1 and rob2 I get lost because for me this is no DP anymore...
Am I wrong?
DP can be stored in an array that is the length of what you know the final result set should be
BUT
To save space you're encouraged to only use what you need, of course, and in many DP problems you only need a subset of the full array
(See Fibonacci DP...you only need the last 2 computed values)
if I want to do this problem by recursion and memoisation, what would be the code
lightbulb went off for me @ 9:30 . thank you dude
Glad it was helpful!
How would you change this solution if we can't rob from N adjacent houses? Do i need a more rob variables?
I think so. This is the version optimized for space. Otherwise an array for the total amount of sub problems to solve for is used (number of all houses in this case). In the loop we would use something like arr[n] and arr[n-1] instead of rob1 and rob2 but we use them since we are only checking elements at these two indices at any given time.
What if you have a testcase [2, 1, 3, 4]? By above solution, you will parse 2+3, 1+4 from which we get 5? But shouldn't the answer be 6 ie, (2+4)?
Hey, thanks for explaining these problems, they're incredibly helpful. Just one question: at 5:01 how come it is Rob[1:] and not Rob[1] + Rob[3:] like the previous Max skip?
Thats same thing im trying to figure out
@@marcusplenty1153 he’s just writing the relation between n to the rest of the array. If you rob the current house (i) then you can’t rob the next (i+1), but you can rob i+2.
From i:n, It’s possible youll solve some of the same sub problems as 2:n. Thus the DP solution to cache your result.
Again rob index to n in this recurrence relation will break down all the way to the last house and pack on the way back finding the max between picking the current house or not)
This method of resolutions make me think of the concept of two pointer or even sliding windows.
Hi, great video! A thought I had after the solution: If I want also to return wish houses to be robbed, you know how I could do that?
you have explained this problem so well.
Thanks 😊
@@NeetCode so time is O(n) and space is O(1)?
One thing that should be called out here is the concept of “optimal substructure”.
The reason this works is because when we look at solving the problem at house i, if we know the optimal solution at house i-1 and i-2 then we can always find the optimal solution at house i. This is expressed as
optimalSolution[i] = max(optimalSolution[i - 1], houseValue[i] + optimalSolution[i - 2])
The use of the names “rob1” and “rob2” aren’t very helpful IMO to understand what we are actually storing in those variables, which is the optimal solution at the 2 prior positions.
does your logic works if we have values
15,7,9,100,1?
I still have a hard time understanding how the code addresses the adjacency constrain. Nothing in the code looks at the indexes, or tracks whether or not we have already robbed the index before the current one.
I find your approach helpful but there is one important thing missing: prove correctness. How do you guarantee that the algorithm computes the correct answer?
So, it’s essentially “max fibonacci” with random values :o
Thanks a lot man!
I just did not understand that when you initialised rob1, rob2 to 0 then in the example which you gave how will rob1 and rob2 be at index 0 and 1, they both should be at index 0 only right? and also after you wrote n in nums then n will also start from 0, but you wrote that n will start after rob1 and rob2. please explain i am really confused. Thanks in advance
Just a stupid question, but why we cannot just run two loops, one from the 0th index and one from the 1st index, skipping the adjacent elements and calculate the sum in two variables and return the max of the two ?
Attempted this myself on LC and realized it's because there will be certain cases in which that answer will not be optimal/correct. For example, that approach will be correct if the input array was [1, 2, 3, 1] (return 4, which is the first and third elements together, which is larger than 3 which is the second + fourth elements). But if the input array is [2, 1, 2, 4], that approach will return 5 (second+ fourth elements, larger than first+third = 4) when the answer should be 6 (first+ fourth elements). In other words there will be input cases in which its is more beneficial to not rob the immediate next non-adjacent house.
This is a Medium now
I am still so confused about this solution of code from rob1 = rob2. Am I stupid even I have watched this video for many times. Hmmmmm. And the important thing is, how can we know rob1 is before rob2. They are all equal to 0. and neetcode said this [rob1, rob2, n, n + 1,...], but before he wrote this list, he said rob1 and rob2 should be at last. how can these two change to the first one and second one? I am so confused. OMG. Gonna die.
I was able to device a recursive brute force solution, but I could never come up with DP. How yall figured this solution out?
excellent explanation
what was the other version of leetcode where you used to solve problems which has like the premium version questions for leetcode for free
I just watched the beginning of the explanation and then went on with trying to understanding on my own. At the end my code used the bottom-down approach you seem to refer to in the explanatory part: recursive calls and memoization with Python dictionaries (without it, LeetCode gave me time limit exceeded). But I want to understand your code, which seems a bit unintuitive to me.
MAN I LVOE YOUR VIDEOS!!!
I was about to give up and look at the solution. Then I found that it was once tagged as an easy problem (it's medium now). I looked at my code once again and found the solution.
Got a similar problem, but the robber cannot rob up to K consecutive houses. Do you have any solution? nice explaination btw
@duong Tran: I guess it shud be similar with the above stated problem of 2 consecutive. No change in recurrence
@@abhishekpawar8458 figured it out, pretty messy but it does the job xD
@@duongtran642 glad to hear !
Thanks for the videos, neat expiation👍
What’s happens (3,2,2,3)
6
How do you come up with this solutions ))) This is amazing
the naive way of thinking about this problem: dp[i] = max(arr[i] + dp[i - 2], dp[i - 1]), dp[i] stands for at position i, the max profit we can get.
neet just uses the bottom-up solution plus the var1 and var2 for recording its status, since at each position, we don't need the whole arr, just its two previous positions.
I just solved this question in neetcode but I'm not sure this is actually a correct solution in all cases. Maybe I'm missing something, but what happens if we have an array like [9, 2, 3, 10, 4, 7]? In that case the best solution would be to pick 9, 10, and 7, jumping over both 2 and 3. I'm not sure this solution would pick up those houses. This is what I came up with (in C#):
public class Solution {
public int Rob(int[] nums) {
var accum = new int[] {0, 0, 0};
for (int i = nums.Length - 1; i >= 0; i--) {
var curr = nums[i] + Math.Max(accum[1], accum[2]);
accum[2] = accum[1];
accum[1] = accum[0];
accum[0] = curr;
}
return Math.Max(accum[0], accum[1]);
}
}
what's the time and space?
So elegant!
Do you know what kind of questions Apple likes? I have technical coding interview in 2 days?
shouldn't just adding alternate set of numbers be enough?
Good thought, but a counter example would be this [9, 1, 1, 9]
In this case we skip both middle values.
I had the exact same thought like you but it just did not work.
You’re a god man.
why you just couldnt calc option1 run and all 0..n+1 and 1..n+2 and then send the max?
why did they change the difficulty to medium?😆😆
Easy Problem ??? Excellent Explanation
it was medium for me xd
brilliant！
if you have used an example like nums =[ 3,1,4,14] , then it would have helped much more as I am still trying to figure out how this example would have been solved.
Thanks for this video though !!
11
yo neetcode can you return to typing with this keyboard? its so relaxing man...
8:40 ❤️❤️
i love your diagram