House Robber

Problem

https://leetcode.com/problems/house-robber/

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

Pattern

Array, Dynamic Programming

Approaches

Dynamic Programming

Explanation

Observe that for each house, we have two options: either rob it or skip it. If we rob it, we cannot rob the previous house but we can rob the house two doors down. Thus the maximum amount we can rob from the first i houses is

money[i] = max(money[i - 1], money[i - 2] + nums[i])

The base case is money[0] = nums[0] as we can only rob the first house. For money[1], note that money[i - 2] is out of bounds. We can only rob either the first or second house, so money[1] = max(nums[0], nums[1]).

We can use dynamic programming to compute the maximum amount of money we can make. To reduce the lines of code, we can use the ternary operator to handle the i = 1 case.

money[i] = max(money[i - 1], (money[i - 2] if i > 1 else 0) + nums[i])

The final answer is money[-1].

Code

def rob(nums: list[int]) -> int:
    """Returns the maximum amount of money that can be made by robbing houses
    with ``nums`` money.
    """
    money = [0] * len(nums)
    money[0] = nums[0]
    for i, n in enumerate(nums):
        money[i] = max(money[i - 1], (money[i - 2] if i >= 2 else 0) + n)

    return money[-1]

Test

>>> from house_robber__dynamic_programming import rob
>>> rob([1, 2, 3, 1])
4
>>> rob([2, 7, 9, 3, 1])
12

Complexity

\(n\) is the number of elements in nums

Measure	Complexity	Notes
Time	\(O(n)\)	one pass through the array
Auxiliary Space	\(O(n)\)	array for storing the maximum amount of money we can rob from the first `i` houses

house_robber__dynamic_programming.rob(nums: list[int]) → int: Returns the maximum amount of money that can be made by robbing houses with nums money.