House Robber: the two-step DP pattern that skips adjacency

The previous article ended with House Robber listed as a related problem: "you cannot rob two adjacent houses; dp[i] = max(nums[i] + dp[i+2], dp[i+1])". That line does the heavy lifting, but it glosses over the part that actually takes time to click — why the adjacency constraint collapses into two variables and nothing more.

The problem

You are a professional robber planning to rob houses along a street. Each house holds some amount of money, but adjacent houses have linked security systems — robbing two houses next to each other will automatically alert the police. Given the integer array nums where nums[i] is the money in house i, return the maximum amount you can rob without alerting the police. Full statement: LeetCode 198.

Constraints:
- 1 <= nums.length <= 100
- 0 <= nums[i] <= 400

The constraint that makes this interesting

You have a row of houses. House i holds nums[i] dollars. You can rob any subset of houses you like, except you cannot rob two directly adjacent ones. The problem asks for the maximum total you can steal.

The constraint is the entire problem. Without it, you'd just sum nums and walk away. The adjacency rule means every decision at house i branches: either you take house i and skip house i-1, or you skip house i and keep whatever you had through house i-1. Those are the only two options.

The constraints tell a quiet story: 1 <= nums.length <= 100 and 0 <= nums[i] <= 400. A hundred houses, each worth at most 400 dollars. The small array size means even O(n^2) would pass — but the DP recurrence runs in O(n) anyway. The non-negative values matter more than they look: they guarantee you never gain by intentionally skipping a house you could take without triggering the alarm. The branching is forced purely by adjacency, not by negative values making some houses worth avoiding on their own merits. If values could go negative, the whole problem would change shape.

nums = [2, 7, 9, 3, 1] — optimal is 2 + 9 + 1 = 12. Rob houses 0, 2, and 4, skipping 1 and 3.

nums = [1, 2, 3, 1] — optimal is 1 + 3 = 4. Skip house 1 (value 2) to grab house 2 (value 3).

From Min Cost Climbing Stairs to House Robber

Min Cost Climbing Stairs had dp[i] = cost[i] + min(dp[i+1], dp[i+2]). The shape is a two-step lookback: from position i, you look one or two positions ahead and combine the results.

House Robber has exactly the same shape, flipped in direction and with max instead of min. Define dp[i] as the maximum loot available from houses 0 through i. At each house:

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

Left branch — skip house i: whatever the best was through house i-1. Right branch — rob house i: you must have skipped house i-1, so the best you had was through house i-2, plus nums[i].

The recurrence is complete. There are no other cases.

Approach 1: Recursive brute force — O(2^n)

Start at index 0 and branch at every house. Take it or skip it.

class Solution:
    def rob(self, nums):
        def robFrom(index):
            if index >= len(nums):
                return 0
            rob_current = nums[index] + robFrom(index + 2)
            skip_current = robFrom(index + 1)
            return max(rob_current, skip_current)
        return robFrom(0)

public class Solution {
    public int Rob(int[] nums) {
        return RobFrom(nums, 0);
    }
    private int RobFrom(int[] nums, int index) {
        if (index >= nums.Length) return 0;
        int robCurrent = nums[index] + RobFrom(nums, index + 2);
        int skipCurrent = RobFrom(nums, index + 1);
        return Math.Max(robCurrent, skipCurrent);
    }
}

Each call branches into two, and you reach base cases at depth n. The call tree has O(2^n) nodes. Call stack depth is O(n). This gets rejected on any input over ~30 houses — not because the problem constraints are large enough to force it, but because the exponential blowup is real and the pattern is the wrong instinct to carry forward.

The issue is overlapping subproblems. To see it concretely, trace the recursion tree for nums = [2, 7, 9, 3, 1]:

robFrom(3) appears three times (yellow nodes). robFrom(4) appears three times. Every shared subproblem gets recomputed from scratch. The brute force has no memory of work already done.

Approach 2: Memoization — O(n) time, O(n) space

Cache the result on the first visit and return it immediately on subsequent ones.

class Solution:
    def rob(self, nums):
        memo = {}
        def robFrom(index):
            if index in memo:
                return memo[index]
            if index >= len(nums):
                return 0
            rob_current = nums[index] + robFrom(index + 2)
            skip_current = robFrom(index + 1)
            memo[index] = max(rob_current, skip_current)
            return memo[index]
        return robFrom(0)

public class Solution {
    private Dictionary<int, int> memo = new Dictionary<int, int>();
    public int Rob(int[] nums) {
        memo.Clear();
        return RobFrom(nums, 0);
    }
    private int RobFrom(int[] nums, int index) {
        if (memo.ContainsKey(index)) return memo[index];
        if (index >= nums.Length) return 0;
        int robCurrent = nums[index] + RobFrom(nums, index + 2);
        int skipCurrent = RobFrom(nums, index + 1);
        memo[index] = Math.Max(robCurrent, skipCurrent);
        return memo[index];
    }
}

Each index from 0 to n-1 is computed once. The dictionary adds O(n) space; the call stack adds another O(n). This works and passes the judge. The memoization approach is useful for understanding the recurrence because it mirrors the branching logic directly. But I wouldn't submit this — the iterative version is simpler to reason about and has no recursion overhead.

Approach 3: Tabulation (bottom-up DP) — O(n) time, O(n) space

Fill a dp array left-to-right. The base cases need a little care for the first two houses.

class Solution:
    def rob(self, nums):
        n = len(nums)
        if n == 0: return 0
        if n == 1: return nums[0]
        dp = [0] * n
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])
        for i in range(2, n):
            dp[i] = max(dp[i-1], dp[i-2] + nums[i])
        return dp[n-1]

public class Solution {
    public int Rob(int[] nums) {
        int n = nums.Length;
        if (n == 0) return 0;
        if (n == 1) return nums[0];
        int[] dp = new int[n];
        dp[0] = nums[0];
        dp[1] = Math.Max(nums[0], nums[1]);
        for (int i = 2; i < n; i++)
            dp[i] = Math.Max(dp[i-1], dp[i-2] + nums[i]);
        return dp[n-1];
    }
}

dp[1] = max(nums[0], nums[1]) deserves a moment. With two houses, you pick the more valuable one — you can't take both. This is the only place where the "skip adjacent" rule produces a choice between two specific values rather than two recurrence branches.

The full trace for nums = [2, 7, 9, 3, 1]:

Answer: 12. Houses 0, 2, 4.

Each step at index i asks one question: is dp[i-1] (leave house i alone) better than dp[i-2] + nums[i] (rob house i)? Nothing else matters. If you ever need to reconstruct which houses were robbed rather than just the total, the dp array is what you trace backward through — so the O(n) space actually earns its keep in that variant.

Approach 4: Space-optimized DP — O(n) time, O(1) space

The tabulation array is O(n), but the recurrence only ever looks at two positions back. Everything before dp[i-2] is dead weight. Replace the array with two scalars.

class Solution:
    def rob(self, nums):
        n = len(nums)
        if n == 0: return 0
        if n == 1: return nums[0]
        prev2 = nums[0]
        prev1 = max(nums[0], nums[1])
        for i in range(2, n):
            current = max(prev1, prev2 + nums[i])
            prev2 = prev1
            prev1 = current
        return prev1

public class Solution {
    public int Rob(int[] nums) {
        int n = nums.Length;
        if (n == 0) return 0;
        if (n == 1) return nums[0];
        int prev2 = nums[0];
        int prev1 = Math.Max(nums[0], nums[1]);
        for (int i = 2; i < n; i++) {
            int current = Math.Max(prev1, prev2 + nums[i]);
            prev2 = prev1;
            prev1 = current;
        }
        return prev1;
    }
}

prev2 is dp[i-2]. prev1 is dp[i-1]. current is dp[i]. After computing current, slide the window forward: prev2 = prev1, prev1 = current. The order matters — prev2 needs the old prev1 before prev1 is overwritten, so update prev2 first.

This is the version I'd ship.

Complexity at a glance

Edge cases

nums = [1] — single house. The n == 1 guard returns nums[0] before the loop even starts. Without the guard, prev1 = max(nums[0], nums[1]) would index out of bounds.

nums = [1, 2] — two adjacent houses. Returns max(1, 2) = 2. The dp[1] = max(nums[0], nums[1]) base case (or prev1 initialization) handles it; the loop body never executes because range(2, 2) is empty.

nums = [2, 1, 1, 2] — symmetric array. Rob houses 0 and 3: 2 + 2 = 4. No special-casing; the recurrence arrives at dp = [2, 2, 3, 4] naturally. At index 3, dp[1] + nums[3] = 2 + 2 = 4 beats dp[2] = 3.

nums = [0, 0, 0] — all zeros. The recurrence produces all zeros and returns 0. No edge-case logic needed; non-negative values guarantee the result is always >= 0.

The non-negative constraint (0 <= nums[i] <= 400) is what makes the recurrence clean. If values could go negative, a house might be worth actively avoiding even without the adjacency rule, and you'd need a richer state. Non-negative values collapse that dimension: the only reason to skip house i is adjacency to house i-1, full stop.

Pattern recognition

The keywords that flag this recurrence: "maximum", "cannot take adjacent elements", "optimal choice at each position". More broadly, any problem where:

• You have a linear sequence of decisions.
• Taking element i forecloses element i-1 (or some fixed-size neighborhood).
• You're maximizing or minimizing a sum over the chosen elements.

When you see all three, reach for the two-step lookback first. Write the brute-force recursion to confirm the recurrence, memoize it to check correctness efficiently, then convert to bottom-up and compress to two variables.

The same skeleton in four sibling problems

House Robber II (213) — the houses form a circle, so house 0 and house n-1 are adjacent. You can't use the same single-pass solution directly. The trick: run the space-optimized rob on nums[0..n-2] and separately on nums[1..n-1], then take the max of both. Same recurrence, two invocations.

House Robber III (337) — houses are arranged in a binary tree. Adjacent now means parent-child. The two-variable trick doesn't port directly; you carry a (rob, skip) pair up from each subtree via post-order DFS. The recurrence logic is identical — rob this node and take the skip-values of both children, or skip this node and take the max of each child — but the data structure changes.

Delete and Earn (740) — you can't take a number if you've already taken a number one less or one greater. Once you notice that it's equivalent to a bucket array where taking bucket i forbids buckets i-1 and i+1, it reduces directly to House Robber. The adjacency constraint is the same; the representation is different.

Decode Ways (91) — linear DP with decision-making at each position. The recurrence shape differs, but the pattern of "at each index, decide based on a fixed lookback window" is the same instinct.

The thread connecting them: any time you have a sequence where taking element i forecloses some set of neighbours and you're optimising a sum, the two-step lookback is worth trying first.