1D Dynamic Programming (House Robber)

The House Robber problem is a classic 1D dynamic programming problem where each decision affects future choices. It teaches how to model mutually exclusive decisions and choose an optimal outcome.

Problem Statement

You are given a list of non-negative integers where each value represents the amount of money in a house along a street.

Rules:

• You cannot rob two adjacent houses
• Maximize the total amount robbed

Example

Input:  [2, 7, 9, 3, 1]
Output: 12

Explanation:

• Rob house 1 (2)
• Rob house 3 (9)
• Rob house 5 (1)

Total = 2 + 9 + 1 = 12

Key Insight

At each house, you have two choices:

1. Rob this house → skip the previous one
2. Skip this house → take the best up to the previous one

This leads to the recurrence:

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

DP State Definition

Let:

dp[i] = maximum amount that can be robbed from houses [0..i]

Base Cases

dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])

Bottom-Up DP (Tabulation)

Rust Implementation

pub fn rob(nums: &[i32]) -> i32 {
    let n = nums.len();

    if n == 0 {
        return 0;
    }
    if n == 1 {
        return nums[0];
    }

    let mut dp = vec![0; n];
    dp[0] = nums[0];
    dp[1] = nums[0].max(nums[1]);

    for i in 2..n {
        dp[i] = dp[i - 1].max(dp[i - 2] + nums[i]);
    }

    dp[n - 1]
}

Space Optimization (O(1) Space)

We only need the previous two states.

pub fn rob_optimized(nums: &[i32]) -> i32 {
    let mut prev2 = 0; // dp[i - 2]
    let mut prev1 = 0; // dp[i - 1]

    for &money in nums {
        let current = prev1.max(prev2 + money);
        prev2 = prev1;
        prev1 = current;
    }

    prev1
}

Example Usage

fn main() {
    let houses = vec![2, 7, 9, 3, 1];
    println!("Max robbed: {}", rob(&houses)); // 12
}

Time and Space Complexity

Time Complexity

Space Complexity

Why This Problem Matters

House Robber introduces an important DP pattern:

At each step: choose between taking or skipping

This exact pattern appears in:

• Maximum sum of non-adjacent elements
• Scheduling problems
• Stock buy/sell (variants)
• Circular House Robber (House Robber II)

Common Mistakes

• Forgetting base cases
• Mixing up indices
• Using greedy instead of DP
• Not considering empty input

Summary

• House Robber is a decision-based 1D DP problem
• Each choice affects future options
• Simple recurrence with powerful implications
• Easily optimized to constant space