House Robber

Dynamic Programming1D DP

20 min

Problem Statement

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

Example 1:

Optimal solution: Rob houses 1, 3, and 5.

Total: $12

Solution

This problem is a classic example of dynamic programming. We can solve it by building up a solution from smaller subproblems. Let `dp[i]` be the maximum amount of money that can be robbed from the first `i` houses.

For each house `i`, we have two choices: either rob it or not. If we rob house `i`, we cannot rob house `i-1`, so the total amount would be `nums[i] + dp[i-2]`. If we don't rob house `i`, the total amount would be `dp[i-1]`. So, the recurrence relation is `dp[i] = max(nums[i] + dp[i-2], dp[i-1])`.

Algorithm Steps (DP)

Create a DP array of size `n+1`, where `n` is the number of houses.
Initialize `dp[0] = 0` and `dp[1] = nums[0]`.
Iterate from `i = 2` to `n`.
`dp[i] = max(dp[i-1], dp[i-2] + nums[i-1])`.
The final answer is `dp[n]`.

Recurrence Relation

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

House 1

House 2

House 3

House 4

House 5

DP Table

Step: 1 / 7

House Robber Solution


def rob(nums: list[int]) -> int:
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]

    # dp[i] will store the maximum amount of money that can be robbed up to house i.
    dp = [0] * len(nums)

    # Base cases
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])

    for i in range(2, len(nums)):
        # For each house, we have two choices:
        # 1. Rob the current house (nums[i]) + the max money from two houses before (dp[i-2]).
        # 2. Don't rob the current house, so we take the max money from the previous house (dp[i-1]).
        dp[i] = max(dp[i-1], dp[i-2] + nums[i])

    return dp[-1]