LeetCode 198. House Robber (Algorithm Explained)

Preparing For Your Coding Interviews? Use These Resources
————————————————————

Other Social Media
----------------------------------------------

Show Support
------------------------------------------------------------------------------

#coding #programming #softwareengineering

[djBC]

yo you should have kept the robber mask while doing the question

[guitarvoicing]

This in old and I don't know if you ever read your subscribers comments, but I have to tell you one amazing thing about you. You have an incredible talent to explain complicated things in a very simple way. Yet, there is an extra impressive feature on your methodology of explaining things. You explain them really fast. Normally, one expect to make it more difficult to follow. But it is the other way around with your videos. You explains things very fast *AND* make them easy to understand. I don't think you even realize this. It is a bit antagonist, how can you explain it so well and so fast? But, man it works great. Thanks for posting these solutions with fast and easy explanations.

[ryan.aquino]

Explaining the template for dynamic programming did helped me.

[quangvo]

Hi Nick, can you create a path or a map for beginners to follow which algorithm /data structure should they learn first and what problems should they do first.

[oscaropdyou]

Thanks for the video. Here is slightly modified/improvised code:
int dp[] = new int[nums.length];
dp[0] = nums[0]; dp[1] = Math.max(dp[0], nums[1]);
for(int i=2; i<nums.length; i++) {
dp[i] = Math.max(nums[i]+dp[i-2], dp[i-1]);
}
return dp[nums.length-1];

[emmanuelonwumah]

You lost me from 8:47 to 9:52 and sadly that the most important part :(

[dera_ng]

I find it easier to solve the problems after understanding a task via a decision tree. However after building out the decision tree and seeing that max_money_stealable is dependent on amount of money the robber has stolen so far, it became pretty difficult to move forward with.

For those who have MASTERED DP, this is probably an easy problem. For those that are still looking for easily digestible/understandable material on this topic called "Dynamic Programming", it's not easy.

[kittwwang]

The template is really helpful! Very clear explanation again!

[fireflygod]

Hello Nick. You explained this very nicely. Could you please make a playlist exclusively for Dynamic Programming problems? That would be extremely helpful. Thanks.

[PRVLEED]

Great explanation. I like how you made clear what the template was for a dp problem.

[LoXatoR]

I think apart from Fibonacci, this is the first time I truly understood a DP problem, even though its considered Easy. Thank you Nick, You explain really really well!

[nevikgnehz]

11:00 There should be 4 elements. On line 5 you declared nums.length + 1 so [1, 2] should be of array size of 3 and since array is zero based it goes from 0th index to 3rd which is total of 4 spaces.

[chelseakatsidzira]

you really have a gift for this. i've been struggling to understand this when all i had to do was watch a couple of your videos to get it. THANK

[BigBobEdyS]

Finally i understood this problem! Thank you... Also the fact that you used an array instead of a variable to show the progression of the maxvalue helped to understand

[andreandrews]

Could have used Kadane's Algorithm to do this in O(1) space :) with the same runtime
if (nums.Length == 0) return 0;
if (nums.Length < 2 ) return nums[0];
int ans = Math.Max(nums[0], nums[1]);
int a = nums[0];

for (int i = 2; i < nums.Length; i++)
{
var temp = Math.Max(ans, a + nums[i]);
a = ans;
ans = temp;
}

return ans;
^^ for reference if anyone was wondering (C#) implementation

[SudhanshuSrivastavaIndia]

Hey Nick,
Just curious why we need an array "dp" when we already know that last element is going to be the result. Can we simply have 2 variables one to store prev-result and another for fina-result and do the same thing. Help me if I am missing anything...

func rob(_ nums: [Int]) -> Int {
guard nums.count > 0 else { return 0 }
var prevResult: Int = 0
var result: Int = nums[0]

for i in 1..<nums.count {
let max = max(result, prevResult + nums[i])
prevResult = result
result = max
}
return result
}

[sophia]

Can you please explain why the templet always set as int dp[] = new int [nums.length + 1]? What does mean to add 1? I still don't understand.

[prepat]

dude i'm literally only applying for SWE internship as a college junior and most of my OAs had dynamic programming. I'm not even joking.

[dalgonacovfefe]

Did you ever end up doing that video on the main types of problems and how to spot them?

[ahmedz]

Nick I dont usually comment but this was a really good video. I’ve seen videos before about dynamic programming but they all made it seemed like this really advanced topic for no reason. When its just storing values in an array. Please make more videos just explaining each category of problems in simple terms this video was really helpful. 👍