Leetcode 198. House Robber

While solving leetcode 21 days challenge I came across house robber problem. Here’s my very simple answer to solve this problem.

Question:

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

Example 2:

Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.

Constraints:

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 400

Intuition

So by reading the question what I can understand is this is a modification of Fibonacci number problem. The only variation I can see is I can’t pick a number which are next to each other. However I can pick something prior to it. Let’s try to solve this problem with tabular variation of dynamic programming.

If you want to learn more about tabular form of dynamic programming refer to my old article

The reason as to why I am pre-calculating the value at index 2 is because it as at a very weird spot. If we start our loop from index 2 we would encounter IndexOutOfBoundException. Thus we are going to calculate it before we start looping.

dp[i] = Math.max(dp[i-2],dp[i-3]) + nums[i];

This is the driving logic of our dp. Where we are checking which is the best to consider with a gap of 1 and this is how we fill our dp table. Last but not least we return the maximum of n or n-1 .

Oh wait, what about the boundary condition

if you look at the constraints we can see that we might have 0 or 1 house in our array.

So incase if there are no house the robber won’t be able to have any profit. If there is only 1 house than whatever you have in your array that is your profit. However if there are only two houses the robber has to two choose between which house will yield the maximum profit and that’s it that’s all we need.

And here’s our final piece of code.

So the time complexity of this would be 0(n) and the space complexity would be 0(n) to store the computed result.

That’s it folks for today. I hope this post helped you in your journey. Comment your thoughts or your question so I can answer them. And if you want me to cover some more dynamic programming strategy hit the clap button and share some love.