Medium

House Robber

062

Return the maximum amount that can be robbed without robbing adjacent houses.

EXAMPLES

Example 1

Input
{
  "nums": [
    1,
    2,
    3,
    1
  ]
}

Output
4

FUNCTION SHAPE

nums: intArray→int

SOLUTION NOTE

Take or don't take pattern. dp(i) = max profit from houses [0..i]. Either rob house i (get nums[i], skip i-1, recurse on i-2) or don't rob (recurse on i-1).

Reveal reference solution +

pythonREFERENCE

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

TimeO(n)

SpaceO(n)

Open on LeetCode ↗