House Robber - Leetcode 198 - Python Dynamic Programming

[@NeetCode]

🚀 neetcode.io/ - A better way to prepare for Coding Interviews

[@DarrienGlasser]

Good playlist 👍

[@jaymistry689]

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.😂😂😂😂

[@symbol767]

I robbed my entire neighborhood thanks to this video. Posting this from jail though

[@albertd7658]

sorry but told you to optimize first

[@eobardthawne6903]

You didn't optimize property bro

[@fenrirgreyback101]

Wow, can’t believe you robbed from two adjacent houses

[@mdk124]

Thanks to leetcode i've given up working as a software engineer, I am now a professional house robber.

[@xavierxavier3610]

This video really helped a lot! Thanks to you, I've gotten away with multiple house robberies.

[@Arcvx]

💀

[@pragyan394]

Had us in the first half, not gonna lie

[@ahulanand4959]

🤣🤣🤣🤣

[@Mylo_madness03]

😂😂😂😂

[@AshishSarin1]

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

[@sonicspider49]

what was your solution if you don't mind me asking?

[@si2]

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

[@kartikag01]

you inspired me bro.

[@aaronhanson1694]

I like how they upgraded this to medium haha

[@gamingislove3030]

😂😂

[@X_platform]

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.

[@rc-zl9dp]

It clicked for me after reading this comment, thanks!

[@yash7241]

this helps

[@derpy566]

Thanks, went from math brain to programming brain

[@DavidDLee]

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.

[@brecoldyls]

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!

[@advaittumbre193]

you are not alone!! xD

[@heyquantboy]

Look up 'mental block' in the dictionary, you'll find my face next to it.

[@medsabkhi]

same!!

[@kimberlygovea8591]

Wow me too! TT^TT im not alone on this DP mental block

[@gan7940]

@@kimberlygovea8591 did you get better?

[@amogchandrashekar8159]

Thanks for listening, and adding a dp question! Though I had solved this before, learnt a ton from this one! Thank you @NeetCode.

[@stcattc]

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.

[@edsalazar4590]

Good to know there's an actual algorithm for robbing houses!

[@JimmyCheng]

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.

[@rabbyhossain6150]

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])

[@bizman7485]

That’s how I did it. I thought it was pretty optimized. But the way Neet did it has an O(1) space complexity

[@Fran-kc2gu]

​​​@@bizman7485Considering you're only adding a 0 and making in place updates, I would also consider this one Space O(1)

[@aumrudhlalkumartj1948]

Thanks! Leetcode changed this problem to medium difficulty 😃

[@jrose2082]

this is the first time, even after completing a whole CS degree, that I understood dynamic programming

[@Mauglus]

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!

[@chiatientsai4070]

Your explanation is the clearest explanation that I had ever found! thank you so much!

[@josembass]

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.

[@andrepinto7895]

you can even use the nums argument directly.

[@kaka83185]

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]

[@psibarpsi]

That was cool - doing it in O(1) space.

[@CostaKazistov]

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).

[@kushalbhargava8212]

It took me a whole day to understand the solution, thank you for putting out this series 😊

[@mengdizheng1223]

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 .

[@hackytech7494]

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 ♥

[@NathanZheng]

Amazing. I tried memoization which also worked. But your solution's conciseness is simply wow

[@TheMadisonBluesBand]

Same. But I'm struggling to edit the recursive solution for House Robber 2

[@mso4324]

I was struggling with understanding solutions in the forum, this really helped clarify how recurrence relation is working here

[@dipsrips]

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.

[@cachestache2485]

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.

[@taroserigano6546]

this makes more sense, thanks !

[@wintersol9921]

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.

[@snoowwe]

I am dumb, I don't get your explanation at all and it seems I'm the only one, looking at the comments.

[@tucker1351]

you're not the only one!

[@MohammedAli-p7e9d]

I was looking for this comment to express my same feeling 😂💔

[@tharunkumar8133]

can't believe you are writing with a mouse .... Appreciate your efforts dude... Awesome explanation by the way

[@DJ-bo4pz]

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.

[@diegosalasnoain1149]

Great solution and explanation: quite easy to grasp, but how is it related to the dynamic programming approach?

[@炒粿条-b1d]

This is DP coded in bottom-up approach. If top-down, then it will be using recursion

[@tanmoy003]

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

[@aashishKr01]

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; };

[@luisady8990]

The solution, video, and explanation are beautiful.

[@NeetCode]

Thanks 😊

[@mistercosmin3542]

Thank you bro, your video really helped me understand how i should approach dynamic programming problems. Thank you so much again!!!

[@MrSkyS-i5v]

After learning a lot of dynamic programming problems from you.... Today I was able to solve this by myself.

[@prodprotto]

lightbulb went off for me @ 9:30 . thank you dude

[@NeetCode]

Glad it was helpful!

[@peterkim1867]

I understand what you did, but I still don't understand how I can come up with the same solution. Definitely need more practice.

[@JobinJose]

Such great explanation! Thanks mate and keep going

[@radhikashroff2643]

you have explained this problem so well.

[@NeetCode]

Thanks 😊

[@serendipity1328]

@@NeetCode so time is O(n) and space is O(1)?

[@kuljeetkumar4657]

Best man on the earth, clear and crisp solutions. Thankyou so much.🙌🙌👌

[@maxpostsclips2699]

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

[@EmadMokhtar]

I've feedback for you. Once you got into the coding part, you rush to the solution and the code isn't easily described. Dynamic Programming is difficult to teach, so spending more time describing your code solution will make it easier.

[@jrboistombol2810]

Now it's updated to Medium Seems your are correct 👏👏💯

[@aigerimsadyrova6174]

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?

[@wanderingcatto1]

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.

[@bonle3771]

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.

[@herono-4292]

This method of resolutions make me think of the concept of two pointer or even sliding windows.

[@zhenyucheng1567]

excellent explanation, Thanks for the video

[@matthieuguimard2236]

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?

[@dorondavid4698]

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)

[@sharoncohen318]

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.

[@The6thProgrammer]

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.

[@gustavoadolfodiazcamilo2462]

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.

[@crockz0r]

Max is a built in function to get max value from two inputs

[@rahulpadhy847]

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!

[@rahulpadhy847]

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); } }

[@카이트-c8y]

Is this solution also work for if there is negative values?

[@Techgether]

my solution with top down approach dp: (I also did a step by step thought process explanation in leetcode) class Solution: def rob(self, nums: List[int]) -> int: if len(nums) == 1: return nums[0] res = 0 def dp(i): if i < 0: return tmp1, tmp2 = 0, 0 if i + 2 < len(nums): tmp1 = nums[i+2] if i + 3 < len(nums): tmp2 = nums[i+3] nums[i] += max(tmp1, tmp2) dp(i-1) dp(len(nums)-1) return max(nums[0],nums[1])

[@MichaelRicksAherne]

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...

[@AdigoThierry]

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 ?

[@nikhildinesan5259]

Simple clean explanation 🔥🔥... great job man....

[@nateo7045]

So, it’s essentially “max fibonacci” with random values :o

[@vvmanyam1]

I solved it with Recursion but this solution is smart! Thank You.

[@AbhishekMadhu_online]

You are a great human being. Thanks.

[@mnchester]

This is a Medium now

[@vyt1706]

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

[@alekkras3487]

It took me a while to get it... Interesting logic.

[@fabriziopellegrini9517]

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.

[@ancai5498]

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.

[@lautarolombardiborsatto3876]

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?

[@ossyahn]

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]); } }

[@warnercooler4488]

Awesome explanation! Thank you so much!

[@seandean2805]

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)?

[@toremixandbeyond1498]

How would you change this solution if we can't rob from N adjacent houses? Do i need a more rob variables?

[@cwash08]

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.

[@navaneethmkrishnan6374]

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.

[@zakenmaru8612]

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?

[@marcusplenty1153]

Thats same thing im trying to figure out

[@SiLintDeath]

@@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)

[@krishnapanduri7076]

Thanks for the videos, neat expiation👍 What’s happens (3,2,2,3)

[@Ritesh_2401]

6

[@benpurcell591]

It would be good if you started with recursion, then with memorize, then bottom up, to see how you can eventually arrive here rather than jumping straight to the optimal solution.

[@namoan1216]

This is amazing, how could you come up with this ideal

[@neoplumes]

Would this work for [10, 1, 1, 10]? Seems like it's just alternating houses, but in this case, we'd want to rob the first and last house and leave the middle two.

[@kavishshah722]

what was the other version of leetcode where you used to solve problems which has like the premium version questions for leetcode for free

[@v_vijay_krishnan]

I was able to device a recursive brute force solution, but I could never come up with DP. How yall figured this solution out?

[@one4all638]

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 !!

[@glitch4548]

11

[@divyashah8197]

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

[@voltorian-minecraft]

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...

[@danielsun716]

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.

[@akashdeep6115]

does your logic works if we have values 15,7,9,100,1?

[@santoshr4212]

Easy Problem ??? Excellent Explanation

[@martinemanuel8239]

it was medium for me xd

[@duongtran642]

Got a similar problem, but the robber cannot rob up to K consecutive houses. Do you have any solution? nice explaination btw

[@abhishekpawar8458]

@duong Tran: I guess it shud be similar with the above stated problem of 2 consecutive. No change in recurrence

[@duongtran642]

@@abhishekpawar8458 figured it out, pretty messy but it does the job xD

[@abhishekpawar8458]

@@duongtran642 glad to hear !

[@cosmicentity4228]

This man is doing God's work....

[@Asmrnerd10]

MAN I LVOE YOUR VIDEOS!!!

[@paccini1]

Thanks a lot man!

[@asparshraj9016]

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 ?

[@sammmmmich]

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.

[@Daniely-z2k]

why you just couldnt calc option1 run and all 0..n+1 and 1..n+2 and then send the max?

[@akshatbansal4758]

if I want to do this problem by recursion and memoisation, what would be the code

[@akash3662]

shouldn't just adding alternate set of numbers be enough?

[@NeetCode]

Good thought, but a counter example would be this [9, 1, 1, 9] In this case we skip both middle values.

[@wlcheng]

I had the exact same thought like you but it just did not work.

[@hfchen5323]

Basically just 2 options, and pick the max (optimal) of the 2 options, keep choosing between 2 options till the very last step. Why 2 options?: The entire question boils down to [rob the current house or not] like one would do in the actual robbing situation. 1. Rob the current one? Ok you are brave, now your ‘earning’ would be what you have now from your bag (robbed tilled the closest non neighbored house so far) + the new house : in code n+rob1. 2. Don’t rob the current one? Sucker, you are such a loser, but it’s ok, you’ll just have your valuables from your bag: in code rob2 The hard thing is you wanna optimize till the end, but ahhhh your brain omg it’s too much it’s 10 houses! So use a loop to keep telling you the max from current 2 choices. If you always made the right choice, you’ll end up with the final result. Since when you finish robbing (after deciding whether to rob the last one), it depends on the same choice (this house + closest non neighbored house OR only the closest neighbored house ), which also depends on the SAME THING, so keep repeating from start to end. Boom works 🎉

[@EranM]

yo neetcode can you return to typing with this keyboard? its so relaxing man...

[@jrboistombol2810]

Is this bottom to top approach