Medium#1987 min readDynamic Programming1D DPLeetCode

House Robber

Two-variable rolling DP

dp[i] = max(dp[i-1], dp[i-2] + nums[i]). The ‘take or skip’ template.

Published Apr 16, 2026

Problem

A thief wants to rob houses along a street. Each house has some money, but adjacent houses trigger the same alarm if both are robbed on the same night. Given an integer array nums of the money in each house, return the maximum amount you can rob without alerting the police.

Input

nums = [1, 2, 3, 1]

Output

Explanation

Rob house 0 (1) and house 2 (3). 1 + 3 = 4.

Input

nums = [2, 7, 9, 3, 1]

Output

Explanation

Rob houses 0, 2, 4: 2 + 9 + 1 = 12.

Input

nums = [2, 1, 1, 2]

Output

Explanation

Skip houses 1 and 2; rob houses 0 and 3. 2 + 2 = 4.

Intuition

Stand on house i. You have two choices, not one: rob this house or skip it. The recurrence falls out of that choice:

If you rob i, the last house you could have robbed was i - 2. Your best answer is nums[i] + dp[i - 2].
If you skip i, the best answer is whatever you had at i - 1. So dp[i - 1].

Take the max:

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

This is the take-or-skip template — the shape of every decision-per-index DP. #70 Climbing Stairs is the same pattern stripped of the max: there's only one sensible move per state, so the recurrence collapses to a sum. House Robber adds the choice, and with it the max.

Approach

Memoized Recursion

TimeO(n)

SpaceO(n)

Write the recurrence directly. rob(i) is "the best you can do from house i onward". Each state is computed once thanks to the memo. Clear derivation; recursion overhead in practice.

impl Solution {
    pub fn rob(nums: Vec<i32>) -> i32 {
        fn best(i: usize, nums: &[i32], memo: &mut Vec<i32>) -> i32 {
            if i >= nums.len() {
                return 0;
            }
            if memo[i] != -1 {
                return memo[i];
            }
            let take = nums[i] + best(i + 2, nums, memo);
            let skip = best(i + 1, nums, memo);
            memo[i] = take.max(skip);
            memo[i]
        }
        let mut memo = vec![-1; nums.len()];
        best(0, &nums, &mut memo)
    }
}

Rust · runnable

function rob(nums: number[]): number {
  const memo = new Array<number>(nums.length).fill(-1);
  const best = (i: number): number => {
    if (i >= nums.length) return 0;
    if (memo[i] !== -1) return memo[i];
    const take = nums[i] + best(i + 2);
    const skip = best(i + 1);
    memo[i] = Math.max(take, skip);
    return memo[i];
  };
  return best(0);
}

TypeScript · runnable

Bottom-Up DP Array

TimeO(n)

SpaceO(n)

Fill a table from the base cases. Easier to debug than recursion — you can print dp after each step. Same asymptotic cost, no stack frames.

impl Solution {
    pub fn rob(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        if n == 0 {
            return 0;
        }
        if n == 1 {
            return nums[0];
        }
        let mut dp = vec![0i32; 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]
    }
}

Rust · runnable

function rob(nums: number[]): number {
  const n = nums.length;
  if (n === 0) return 0;
  if (n === 1) return nums[0];
  const dp = new Array<number>(n).fill(0);
  dp[0] = nums[0];
  dp[1] = Math.max(nums[0], nums[1]);
  for (let i = 2; i < n; i++) {
    dp[i]= Math.max(dp[i - 1], dp[i - 2] + nums[i]);
  }
  return dp[n - 1];
}

TypeScript · runnable

Two-Variable Rolling

TimeO(n)

SpaceO(1)

Recommended

Each dp[i] only reads dp[i - 1] and dp[i - 2]. The table is overkill — keep two scalars and roll them forward. Same algorithm, less memory, better cache behavior. This is the form to ship.

impl Solution {
    pub fn rob(nums: Vec<i32>) -> i32 {
        let (mut prev2, mut prev1) = (0i32, 0i32);
        for &x in &nums {
            let curr = prev1.max(prev2 + x);
            prev2 = prev1;
            prev1 = curr;
        }
        prev1
    }
}

Rust · runnable

function rob(nums: number[]): number {
  let prev2 = 0;
  let prev1 = 0;
  for (const x of nums) {
    const curr = Math.max(prev1, prev2 + x);
    prev2 = prev1;
    prev1 = curr;
  }
  return prev1;
}

TypeScript · runnable

Starting both variables at 0 makes the empty-array case trivially correct: the loop never runs, prev1 stays 0.

Trace

Rolling form on nums = [2, 7, 9, 3, 1]:

i	nums[i]	prev2	prev1	curr = max(prev1, prev2 + nums[i])
init	—	0	0	—
0	2	0	2	2
1	7	2	7	7
2	9	7	11	11
3	3	11	11	11
4	1	11	12	12

Return prev1 = 12. ✓

Edge cases

nums = [] — return 0. The rolling form handles this implicitly; the table form needs the explicit n == 0 check.
nums = [x] — return x. Table form needs the n == 1 check; rolling form handles it (loop runs once, curr = max(0, 0 + x) = x).
All zeros — return 0. No adjacency constraint kicks in because there's nothing to lose.
Two houses — max(nums[0], nums[1]). The max in the recurrence handles this.

ℹ️

Note

The take-or-skip template generalizes: whenever the problem has "you can do X at each index, but doing it excludes some neighbors," the answer is dp[i] = max(skip_value, take_value + dp[i - k]) where k is the exclusion radius. House Robber uses k = 2; a "no three consecutive" variant would use k = 3.

Takeaway

Every decision-per-index DP reduces to "for each state, what were my options at the previous states?" House Robber has two options per state (take or skip); #70 had one (take whatever step). When you see the shape — a linear scan where each position's answer depends on a small fixed number of earlier positions — the space-optimized rolling form is always available.

The same recurrence comes back in #337 House Robber III (trees instead of arrays, so you track a pair per node) and generalizes further in #152 Maximum Product Subarray (two rolling variables, one for the max-ending-here, one for the min). Keep the template; change the state variables.

Easy#70

Climbing Stairs

Fibonacci in disguise. dp[i] = dp[i-1] + dp[i-2]. Start here.

Medium#337

House Robber III

House Robber on a tree. Return (rob_this, skip_this) pair from each subtree.

Medium#152

Maximum Product Subarray

Track both max AND min at each position (negatives flip signs).