House Robber

TARGET DECK: Leetcode FILE TAGS: Medium

---

Intuition

• For each house, you either rob the house, or you don’t rob the house.
• If you choose not to rob the house, then you can rob the next one.
• If you choose to rob the house, then you can’t rob the next one and must go on to the next next one.
• This can be solved simply recursively, and memoized via a HashMap to return previous computations.

Complexity

Runtime

• $O(N)$ since each each computation will only occur once.

Space

• $O(1)$ since you only need to keep track of previous and previous to previous.
• $O(N)$ space for the DP HashMap.

Code

Bottom Up

No Extra Space

class Solution:
    def rob(self, nums: List[int]) -> int:
        prevprev, prev = 0, 0
        for num in nums:
            prevprev, prev = prev, max(prev, num + prevprev)
        return prev

• On each iteration, rob the previous house, or the current house plus the previous previous house

Tabulation

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [0, 0] + nums
        for i in range(2, n + 2):
            dp[i] = max(dp[i - 1], nums[i - 2] + dp[i - 2])
        return dp[n + 1]

• The “bottom” here refers to the first house that must be robbed.
• That is to say: The first house is robbed, then moving on until the last house where one stops.

Memoization

class Solution:
    def rob(self, nums: List[int]) -> int:
        @cache
        def r(i):
            if i < 0:
                return 0
            return max(nums[i] + r(i - 2), r(i - 1))
        return r(len(nums) - 1)

• Notice here that “top” refers to the last house, since semantically, the robber ends up at the last house after having robbed all the previous houses.

Recursion (TLE)

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        def r(index):
            if index >= n:
                return 0
            return max(nums[index] + r(index + 2), r(index + 1))
        return r(0)

START Basic Front: House Robber Back: You always have the choice of whether to rob the current house or not, and deal with the consequences of that.

END

---

References

• House Robber