MediumBlind75ArrayDP

House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. You cannot rob two adjacent houses. Given an array nums representing the amount of money of each house, return the maximum amount you can rob.

Examples

Input
nums = [1,2,3,1]
Output
4

Rob house 1 (money = 1) and house 3 (money = 3), total = 1 + 3 = 4.

Input
nums = [2,7,9,3,1]
Output
12

Rob house 1 (money = 2), house 3 (money = 9), and house 5 (money = 1), total = 2 + 9 + 1 = 12.

Constraints

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

Approaches

Recursively try robbing or skipping each house.

CodeT: O(2^n) | S: O(n)
def rob(nums):
    def helper(i):
        if i >= len(nums):
            return 0
        return max(nums[i] + helper(i + 2), helper(i + 1))
    return helper(0)

Use DP where dp[i] is the max money robbing up to house i.

CodeT: O(n) | S: O(n)
def rob(nums):
    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], dp[i-2] + nums[i])
    return dp[-1]

Only keep track of the last two values.

Diagram

nums = [2,7,9,3,1] prev2=0, prev1=0 num=2: prev2=0, prev1=2 num=7: prev2=2, prev1=max(2,0+7)=7 num=9: prev2=7, prev1=max(7,2+9)=11 num=3: prev2=11, prev1=max(11,7+3)=11 num=1: prev2=11, prev1=max(11,11+1)=12 Result: 12
CodeT: O(n) | S: O(1)
def rob(nums):
    if not nums:
        return 0
    prev2, prev1 = 0, 0
    for num in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + num)
    return prev1

Complexity Comparison

Recursion
T: O(2^n)S: O(n)

Recursively try robbing or skipping each house.

DP - Bottom Up
T: O(n)S: O(n)

Use DP where dp[i] is the max money robbing up to house i.

Space Optimized
T: O(n)S: O(1)

Only keep track of the last two values.

Common Mistakes

Trying to rob adjacent houses

Not handling the edge case of a single house

Using O(n) space when O(1) is possible

Try It Yourself

Copy the optimal solution and run it in our compiler.

▶Open in Compiler
← All Problems