1D DP Problems - Learning Module

Loading content...

0/276

House Robber Problem

The No-Adjacent Constraint: A New Kind of DP

The House Robber problem introduces a critical constraint that transforms how we think about DP: you cannot select adjacent elements. This seemingly simple rule creates a fundamentally different recurrence structure from Fibonacci or Climbing Stairs.

The Classic Problem Statement (LeetCode 198):

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. Adjacent houses have security systems connected — if two adjacent houses are broken into on the same night, the alarm will trigger.

Given an integer array nums representing the amount of money at each house, return the maximum amount of money you can rob tonight without alerting the police.

This problem forces us to make binary choices at each position (rob or skip) while respecting a non-local constraint (no two adjacent).

What You Will Learn

By the end of this page, you will: (1) Understand how the no-adjacent constraint shapes the DP recurrence, (2) Master the include/exclude decision pattern, (3) Implement optimal O(n) time and O(1) space solutions, (4) Extend to circular arrays (House Robber II), (5) Handle tree structures (House Robber III preview), (6) Recognize this pattern in diverse problems like stock trading and scheduling.

Breaking Down the Problem

Let's analyze the House Robber problem systematically before jumping to code.

Core Observations:

Binary Decision at Each House: For each house i, we either rob it or skip it.
The Constraint: If we rob house i, we CANNOT rob house i-1 (or house i+1).
Goal: Maximize total money robbed.
Greedy Doesn't Work: Consider houses with money [2, 7, 9, 3, 1].
- Greedy (always take maximum available): Take 9, then can't take 7 or 3, take 2, take 1 → Total: 12
- Optimal: Take 2, skip 7, take 9, skip 3, take 1 → Total: 12
- But wait: Take 7 + 3 = 10, or Take 2 + 9 + 1 = 12. Actually with [2,7,9,3,1], optimal is 2+9+1 = 12.
- Try [1, 2, 3, 1]: Greedy takes 3, then 1 = 4. Optimal takes 2+1+... wait, let me reconsider.
Actually Greedy CAN Fail: Consider [2, 1, 1, 2]. Greedy might take middle 1 first (if sorting by position), missing optimal 2+2=4.

The key insight is that the decision at position i depends on what we decided for ALL previous positions, not just the immediate predecessor.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
House values: [2, 7, 9, 3, 1]
                  Indices:     [0, 1, 2, 3, 4]
 
Decision tree (R = Rob, S = Skip):
 
                      Start
                    /       \
               R[0]=2         S[0]=0
                /   \          /    \
           must     R[1]=7  R[1]=7   S[1]=0
           skip     (total 7) (7)     (0)
              |        ...      
           S[1]=2    
            /   \   
       R[2]=11  S[2]=2
          ...     ...
 
Optimal path: R[0] → S[1] → R[2] → S[3] → R[4] = 2 + 9 + 1 = 12
Alternative:  S[0] → R[1] → S[2] → R[3] → S[4] = 7 + 3 = 10
Alternative:  S[0] → R[1] → S[2] → S[3] → R[4] = 7 + 1 = 8
 
The tree grows exponentially, but DP collapses it to O(n).

The DP Insight

At each house i, the optimal decision depends only on the maximum money achievable from houses 0 through i-1 (with rob/skip decisions already optimized). We don't need to track the full history — just the best results so far.

Deriving the DP Recurrence

Let's define our DP state and derive the recurrence relation.

State Definition:

Let dp[i] = maximum money robable from houses 0 through i (we can choose to rob any subset of them, subject to the no-adjacent constraint).

The Key Insight:

For house i, we have exactly two choices:

Rob house i: We get nums[i], but we CANNOT have robbed house i-1. The best we can do from houses 0 through i-2 is dp[i-2]. Total: dp[i-2] + nums[i].
Skip house i: We don't get money from house i, but we could have robbed house i-1 if optimal. The best from houses 0 through i-1 is dp[i-1].

The Recurrence:

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

This is beautifully simple: the best up to house i is either the best without house i, or the best without the last two houses plus house i's value.

State Transition Logic
Choice	Money from House i	Previous State Used	Total Formula
Rob house i	nums[i]	dp[i-2] (skip i-1)	dp[i-2] + nums[i]
Skip house i	0	dp[i-1] (could have robbed i-1)	dp[i-1]
Optimal	—	—	max(dp[i-1], dp[i-2] + nums[i])

Base Cases:

dp[0] = nums[0]: With only house 0, we rob it.
dp[1] = max(nums[0], nums[1]): With two houses, rob the richer one.

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

We can only rob one of the first two houses (they're adjacent). So we pick the one with more money. Note: this could also be derived from the recurrence with dp[-1] = 0 as a sentinel:

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

Include/Exclude Pattern

The recurrence dp[i] = max(dp[i-1], dp[i-2] + nums[i]) is the canonical 'include/exclude' pattern. You'll see it in independent set problems, scheduling with conflicts, and many other optimization problems with exclusion constraints.

Complete Implementation — From O(n) Space to O(1)

Let's implement the House Robber solution in progressively optimized forms, following the same pattern we used for Fibonacci.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * House Robber — Basic Tabulation
 * 
 * Time: O(n)
 * Space: O(n) for the DP array
 */
function robTabulated(nums: number[]): number {
    const n = nums.length;
    
    // Edge cases
    if (n === 0) return 0;
    if (n === 1) return nums[0];
    
    // DP array: dp[i] = max money from houses 0..i
    const dp: number[] = new Array(n);
    
    // Base cases
    dp[0] = nums[0];
    dp[1] = Math.max(nums[0], nums[1]);
    
    // Fill the table
    for (let i = 2; i < n; i++) {
        // Choice: skip house i OR rob house i (which requires skipping i-1)
        dp[i] = Math.max(
            dp[i - 1],           // Skip house i: best up to i-1
            dp[i - 2] + nums[i]  // Rob house i: best up to i-2, plus nums[i]
        );
    }
    
    return dp[n - 1];
}
 
// Trace through example [2, 7, 9, 3, 1]:
// dp[0] = 2
// dp[1] = max(2, 7) = 7
// dp[2] = max(7, 2+9) = max(7, 11) = 11
// dp[3] = max(11, 7+3) = max(11, 10) = 11
// dp[4] = max(11, 11+1) = max(11, 12) = 12
// Result: 12

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
 * House Robber — Space-Optimized
 * 
 * Observation: dp[i] only depends on dp[i-1] and dp[i-2].
 * We only need to track the last two values.
 * 
 * Time: O(n)
 * Space: O(1)
 */
function rob(nums: number[]): number {
    const n = nums.length;
    
    if (n === 0) return 0;
    if (n === 1) return nums[0];
    
    // prev2 = dp[i-2], prev1 = dp[i-1]
    let prev2 = nums[0];
    let prev1 = Math.max(nums[0], nums[1]);
    
    for (let i = 2; i < n; i++) {
        const current = Math.max(prev1, prev2 + nums[i]);
        prev2 = prev1;
        prev1 = current;
    }
    
    return prev1;
}
 
// Alternative formulation (arguably cleaner)
function robAlt(nums: number[]): number {
    let robbed = 0;    // Max money if we robbed the previous house
    let skipped = 0;   // Max money if we skipped the previous house
    
    for (const money of nums) {
        // If we rob this house, we must have skipped the previous
        const newRobbed = skipped + money;
        // If we skip this house, we take the best of having robbed or skipped previous
        const newSkipped = Math.max(robbed, skipped);
        
        robbed = newRobbed;
        skipped = newSkipped;
    }
    
    return Math.max(robbed, skipped);
}
 
console.log(rob([2, 7, 9, 3, 1]));  // 12
console.log(rob([1, 2, 3, 1]));     // 4 (1 + 3)
console.log(rob([2, 1, 1, 2]));     // 4 (2 + 2)

State Transition View

•State: dp[i] = best from 0..i
•Transition: max(skip, include)
•Track: Last two dp values
•Natural for: Finding optimal value

Robbed/Skipped View

•State: (robbed, skipped) at each step
•Transition: newRob = skip+val, newSkip = max(rob,skip)
•Track: Two explicit states
•Natural for: Understanding decisions

Two Equivalent Formulations

Both formulations compute the same answer. The first (dp[i-1], dp[i-2]) is more intuitive from the recurrence. The second (robbed, skipped) makes the decision structure explicit and extends more naturally to problems with more states.

Which Houses Did We Rob? Path Reconstruction

Often we need to know not just the maximum value, but which elements we selected. For House Robber, this means determining which houses were robbed in the optimal solution.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
/**
 * House Robber with Path Reconstruction
 * 
 * Returns both the maximum money and the indices of robbed houses.
 * 
 * Time: O(n)
 * Space: O(n) for storing the path
 */
function robWithPath(nums: number[]): { maxMoney: number; robbedHouses: number[] } {
    const n = nums.length;
    
    if (n === 0) return { maxMoney: 0, robbedHouses: [] };
    if (n === 1) return { maxMoney: nums[0], robbedHouses: [0] };
    
    // DP table
    const dp: number[] = new Array(n);
    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]);
    }
    
    // Backtrack to find which houses were robbed
    const robbedHouses: number[] = [];
    let i = n - 1;
    
    while (i >= 0) {
        if (i === 0) {
            // At house 0, we always include it if we reach here
            robbedHouses.push(0);
            break;
        } else if (i === 1) {
            // At houses 0-1, we pick the larger one
            robbedHouses.push(nums[1] > nums[0] ? 1 : 0);
            break;
        } else if (dp[i] === dp[i - 2] + nums[i]) {
            // We robbed house i
            robbedHouses.push(i);
            i -= 2;  // Must skip i-1, go to i-2
        } else {
            // We skipped house i
            i -= 1;
        }
    }
    
    robbedHouses.reverse();
    
    return {
        maxMoney: dp[n - 1],
        robbedHouses: robbedHouses,
    };
}
 
// Example
const result = robWithPath([2, 7, 9, 3, 1]);
console.log("Max money:", result.maxMoney);        // 12
console.log("Robbed houses:", result.robbedHouses); // [0, 2, 4]
 
// Verification: houses [0, 2, 4] have values [2, 9, 1] = 12 ✓
 
const result2 = robWithPath([1, 2, 3, 1]);
console.log("Max money:", result2.maxMoney);        // 4
console.log("Robbed houses:", result2.robbedHouses); // [1, 3] (values [2, 1] = 3... wait)
// Actually let's check: dp = [1, 2, 4, 4]
// Backtrack from i=3: dp[3]=4, dp[1]+nums[3] = 2+1=3, dp[2]=4, so skip 3
// i=2: dp[2]=4, dp[0]+nums[2] = 1+3=4, equal! So we robbed house 2.
// robbedHouses = [2], i becomes 0
// i=0: push 0, break
// robbedHouses = [0, 2], values [1, 3] = 4 ✓

Handling Ties in Backtracking

When dp[i] = dp[i-1] = dp[i-2] + nums[i], there are multiple optimal solutions. The backtracking code above picks one arbitrarily. If you need ALL optimal solutions, you'd need to explore both branches when ties occur.

House Robber II — Circular Street

LeetCode 213 introduces a twist: the houses are arranged in a circle, so the first and last houses are adjacent.

Problem Statement:

All houses are arranged in a circle. The first house is the neighbor of the last one. Constraints remain: cannot rob adjacent houses. Find the maximum money.

The Key Insight:

Since houses 0 and n-1 are adjacent, we cannot rob both. This means valid robberies fall into two categories:

Don't rob house 0: Consider houses 1 through n-1 (linear problem)
Don't rob house n-1: Consider houses 0 through n-2 (linear problem)

The optimal solution is the maximum of these two linear subproblems!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/**
 * House Robber II — Circular Street
 * 
 * The houses form a circle, so house 0 and house n-1 are adjacent.
 * We cannot rob both the first and last house.
 * 
 * Strategy: Run two linear House Robber problems:
 * 1. Houses [0, n-2] (potentially rob first, definitely not last)
 * 2. Houses [1, n-1] (definitely not first, potentially rob last)
 * 
 * Time: O(n)
 * Space: O(1)
 */
function robCircular(nums: number[]): number {
    const n = nums.length;
    
    if (n === 0) return 0;
    if (n === 1) return nums[0];
    if (n === 2) return Math.max(nums[0], nums[1]);
    
    // Helper: solve linear House Robber for a subarray
    function robLinear(start: number, end: number): number {
        let prev2 = 0;
        let prev1 = 0;
        
        for (let i = start; i <= end; i++) {
            const current = Math.max(prev1, prev2 + nums[i]);
            prev2 = prev1;
            prev1 = current;
        }
        
        return prev1;
    }
    
    // Case 1: Possibly rob house 0, definitely skip house n-1
    const case1 = robLinear(0, n - 2);
    
    // Case 2: Definitely skip house 0, possibly rob house n-1
    const case2 = robLinear(1, n - 1);
    
    return Math.max(case1, case2);
}
 
// Examples
console.log(robCircular([2, 3, 2]));    // 3 (rob house 1)
console.log(robCircular([1, 2, 3, 1])); // 4 (rob houses 1 and 3, values 2+1... wait)
// Houses: [1, 2, 3, 1], circular so 0 and 3 are adjacent
// Case 1: houses [0,1,2] = [1,2,3] → rob 1 and 3? No, just [1,2,3], answer = max(1,2,1+3)=4
// Case 2: houses [1,2,3] = [2,3,1] → answer = max(2,3,2+1)=3
// max(4, 3) = 4 ← but this is 1+3 from [1,2,3] subset, which is houses 0 and 2
// Let me redo: houses 0 and 2 in original [1,2,3,1] have values 1 and 3, sum=4 ✓
 
console.log(robCircular([1, 2, 3]));    // 3 (can only rob house 1 for 2, or house 2 for 3... wait)
// Case 1: [0,1] = [1,2] → max(1,2) = 2
// Case 2: [1,2] = [2,3] → max(2,3) = 3
// Answer: 3 (rob house 2)

Reduce Circular to Linear

This 'break the circle by considering two cases' technique appears frequently. For any circular DP problem, identify which elements conflict due to the circular connection, then solve linear subproblems that avoid the conflict.

House Robber III — Tree Structure Preview

LeetCode 337 extends the problem to tree structures. While full tree DP is covered later, this variant demonstrates how the include/exclude pattern generalizes to trees.

Problem Statement:

Houses are arranged in a binary tree. The thief cannot rob two directly-connected houses. Find the maximum money.

The Approach:

For each tree node, we compute two values:

rob: Maximum money if we ROB this node
skip: Maximum money if we SKIP this node

The recurrence:

rob = node.value + skip(left) + skip(right) (if we rob here, we must skip children)
skip = max(rob(left), skip(left)) + max(rob(right), skip(right)) (if we skip, children can be either)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/**
 * House Robber III — Tree Structure
 * 
 * Binary tree where connected nodes cannot both be robbed.
 * 
 * For each node, compute [rob, skip]:
 * - rob: max money if we rob this node
 * - skip: max money if we skip this node
 * 
 * Time: O(n) — visit each node once
 * Space: O(h) — tree height for recursion stack
 */
 
interface TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
}
 
function robTree(root: TreeNode | null): number {
    // Returns [rob, skip] for the subtree rooted at node
    function dfs(node: TreeNode | null): [number, number] {
        if (node === null) return [0, 0];
        
        const [leftRob, leftSkip] = dfs(node.left);
        const [rightRob, rightSkip] = dfs(node.right);
        
        // If we rob this node, we must skip both children
        const rob = node.val + leftSkip + rightSkip;
        
        // If we skip this node, each child can be either robbed or skipped
        const skip = Math.max(leftRob, leftSkip) + Math.max(rightRob, rightSkip);
        
        return [rob, skip];
    }
    
    const [rob, skip] = dfs(root);
    return Math.max(rob, skip);
}
 
// Example tree:
//       3
//      / \
//     2   3
//      \   \
//       3   1
// 
// Nodes at level 0: [3]
// Nodes at level 1: [2, 3]  
// Nodes at level 2: [3, 1]
//
// Optimal: Rob 3 (root) + 3 (left-right grandchild) + 1 (right-right grandchild) = 7
// Or: Rob 2 + 3 (right child) = doesn't work, 2 and its parent 3 are adjacent
// Actually: Rob 3 (root's left's right child) + 3 (root) + 1 = 7
// Or: Skip root, rob 2's subtree (2+3=5) + rob right subtree (3+1=4... but 3 and 1 adjacent!)
// Right subtree: 3 with child 1, rob 3 = 3, skip 3 and rob 1 = 1, so max = 3
// Total if skip root: (skip 2, rob 3 from left = 3) + (rob 3 from right = 3) = no wait
// 
// Let me trace: 
// Node 1 (bottom right): [1, 0]
// Node 3 (right, parent of 1): rob=3+0=3, skip=max(1,0)=1, return [3, 1]
// Node 3 (bottom left of 2): [3, 0]
// Node 2: rob=2+0=2, skip=max(3,0)=3, return [2, 3]
// Node 3 (root): rob=3+3+1=7, skip=max(2,3)+max(3,1)=3+3=6, return [7, 6]
// Answer: max(7, 6) = 7 ✓

Tree DP Pattern

Tree DP typically returns multiple values per node (here [rob, skip]), computed from children's values. This is 'DP on trees' — a powerful technique we'll explore fully in the tree algorithms chapter.

Related Problems — The Include/Exclude Family

The House Robber recurrence — dp[i] = max(dp[i-1], dp[i-2] + value[i]) — is a specific instance of the broader include/exclude pattern. Here are related problems that share this structure:

Include/Exclude Pattern in Various Problems
Problem	Including Element i	Excluding Element i	Constraint
House Robber	dp[i-2] + nums[i]	dp[i-1]	No adjacent elements
Delete & Earn	points[i-2] + total[i]	points[i-1]	Deleting x removes x±1
Best Time Buy/Sell Cooldown	sell[i-1] + prices[i]	cooldown	Cooldown after sell
Maximum Sum No 3 Consec	dp[i-2] + nums[i]	dp[i-1]	No three consecutive
Paint House	cost[i][c] + dp[i-1][c']	—	No same color adjacent

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
 * Delete and Earn (LeetCode 740)
 * 
 * You have an array nums. When you delete element x, you earn x points,
 * but you must also delete ALL occurrences of x-1 and x+1.
 * 
 * Insight: Group points by value, then it becomes House Robber!
 * If we "take" value v, we can't take v-1 or v+1 (adjacent values).
 * 
 * Time: O(n + max(nums))
 * Space: O(max(nums))
 */
function deleteAndEarn(nums: number[]): number {
    if (nums.length === 0) return 0;
    
    // Step 1: Count total points for each value
    const maxVal = Math.max(...nums);
    const points: number[] = new Array(maxVal + 1).fill(0);
    
    for (const num of nums) {
        points[num] += num;  // Each occurrence of num earns 'num' points
    }
    
    // Step 2: House Robber on the points array
    // points[i] = total points from taking all occurrences of value i
    // If we take value i, we can't take i-1 or i+1 (adjacent in value space)
    
    let prev2 = 0;  // dp[i-2]
    let prev1 = 0;  // dp[i-1]
    
    for (let i = 0; i <= maxVal; i++) {
        const current = Math.max(prev1, prev2 + points[i]);
        prev2 = prev1;
        prev1 = current;
    }
    
    return prev1;
}
 
console.log(deleteAndEarn([3, 4, 2]));       // 6: take 2 and 4 (sum 6)
console.log(deleteAndEarn([2, 2, 3, 3, 3, 4])); // 9: take 3s (sum 9)

Recognize the Pattern

Whenever a problem says 'you can't select X and Y together' where X and Y are 'adjacent' in some sense, think House Robber. The 'adjacency' might be in array index, value space, time steps, or even graph structure.

Complexity Analysis and Comparison

Let's formally analyze the complexity of House Robber and compare it to alternative approaches.

Approach Comparison for House Robber
Approach	Time	Space	Practical Limit	Notes
Brute Force (all subsets)	O(2ⁿ)	O(n) stack	n ≈ 20	Exponentially explores all rob/skip choices
Brute Force + Pruning	O(~1.5ⁿ)	O(n) stack	n ≈ 30	Prune invalid (adjacent) states early
Memoization	O(n)	O(n)	n ≈ 10⁵	Cache on index; stack depth limits
Tabulation	O(n)	O(n)	n ≈ 10⁸	No stack; memory limits
Space-Optimized	O(n)	O(1)	n ≈ 10¹²	Only integer limits; essentially unlimited

Why O(n) subproblems?

In House Robber, the current best depends only on position i. The state is uni-dimensional: we only need to know "what's the best up to index i?" to compute "what's the best up to index i+1?"

This gives us n distinct subproblems, each solvable in O(1) time (just a max of two values), yielding O(n) total time.

Why O(1) space is possible?

The recurrence dp[i] = max(dp[i-1], dp[i-2] + nums[i]) has a lookback of 2. We only ever need the previous two values, not the full history. This 'sliding window' over the DP table reduces space from O(n) to O(1).

General Principle: Lookback Determines Space

If a DP recurrence only looks back k steps (for constant k), space can be reduced to O(k). Fibonacci and Climbing Stairs: k=2 → O(1). Some problems have k=O(n), requiring O(n) space regardless.

Summary and Key Takeaways

The House Robber problem family teaches fundamental DP concepts that extend far beyond the specific problem:

Key Takeaways

•The include/exclude pattern: dp[i] = max(dp[i-1], dp[i-2] + value[i]) — choose to include element i (forcing exclusion of i-1) or exclude i.
•No-adjacent constraint: When elements conflict with neighbors, the recurrence naturally looks back two positions.
•Space optimization: Lookback of 2 means O(1) space is achievable with two variables.
•Circular extension: Break the circle by solving two linear subproblems that avoid the first-last conflict.
•Tree extension: Maintain (rob, skip) state pairs; children's skip allows parent's rob.
•Pattern recognition: Many problems (Delete & Earn, stock trading with cooldown) are House Robber with different wording.
•Path reconstruction: Track decisions to recover which elements were selected in the optimal solution.

Page Complete

You've mastered the House Robber pattern and its extensions. The next page consolidates our learning with the unifying concept: the single-index state representation that characterizes all 1D DP problems.

House Robber Problem

The No-Adjacent Constraint: A New Kind of DP

The Classic Problem Statement (LeetCode 198):

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. Adjacent houses have security systems connected — if two adjacent houses are broken into on the same night, the alarm will trigger.

Given an integer array nums representing the amount of money at each house, return the maximum amount of money you can rob tonight without alerting the police.

This problem forces us to make binary choices at each position (rob or skip) while respecting a non-local constraint (no two adjacent).

What You Will Learn

Breaking Down the Problem

Let's analyze the House Robber problem systematically before jumping to code.

Core Observations:

Binary Decision at Each House: For each house i, we either rob it or skip it.
The Constraint: If we rob house i, we CANNOT rob house i-1 (or house i+1).
Goal: Maximize total money robbed.
Greedy Doesn't Work: Consider houses with money [2, 7, 9, 3, 1].
- Greedy (always take maximum available): Take 9, then can't take 7 or 3, take 2, take 1 → Total: 12
- Optimal: Take 2, skip 7, take 9, skip 3, take 1 → Total: 12
- But wait: Take 7 + 3 = 10, or Take 2 + 9 + 1 = 12. Actually with [2,7,9,3,1], optimal is 2+9+1 = 12.
- Try [1, 2, 3, 1]: Greedy takes 3, then 1 = 4. Optimal takes 2+1+... wait, let me reconsider.
Actually Greedy CAN Fail: Consider [2, 1, 1, 2]. Greedy might take middle 1 first (if sorting by position), missing optimal 2+2=4.

The key insight is that the decision at position i depends on what we decided for ALL previous positions, not just the immediate predecessor.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
House values: [2, 7, 9, 3, 1]
                  Indices:     [0, 1, 2, 3, 4]
 
Decision tree (R = Rob, S = Skip):
 
                      Start
                    /       \
               R[0]=2         S[0]=0
                /   \          /    \
           must     R[1]=7  R[1]=7   S[1]=0
           skip     (total 7) (7)     (0)
              |        ...      
           S[1]=2    
            /   \   
       R[2]=11  S[2]=2
          ...     ...
 
Optimal path: R[0] → S[1] → R[2] → S[3] → R[4] = 2 + 9 + 1 = 12
Alternative:  S[0] → R[1] → S[2] → R[3] → S[4] = 7 + 3 = 10
Alternative:  S[0] → R[1] → S[2] → S[3] → R[4] = 7 + 1 = 8
 
The tree grows exponentially, but DP collapses it to O(n).

The DP Insight

Deriving the DP Recurrence

Let's define our DP state and derive the recurrence relation.

State Definition:

Let dp[i] = maximum money robable from houses 0 through i (we can choose to rob any subset of them, subject to the no-adjacent constraint).

The Key Insight:

For house i, we have exactly two choices:

Rob house i: We get nums[i], but we CANNOT have robbed house i-1. The best we can do from houses 0 through i-2 is dp[i-2]. Total: dp[i-2] + nums[i].
Skip house i: We don't get money from house i, but we could have robbed house i-1 if optimal. The best from houses 0 through i-1 is dp[i-1].

The Recurrence:

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

This is beautifully simple: the best up to house i is either the best without house i, or the best without the last two houses plus house i's value.

State Transition Logic
Choice	Money from House i	Previous State Used	Total Formula
Rob house i	nums[i]	dp[i-2] (skip i-1)	dp[i-2] + nums[i]
Skip house i	0	dp[i-1] (could have robbed i-1)	dp[i-1]
Optimal	—	—	max(dp[i-1], dp[i-2] + nums[i])

Base Cases:

dp[0] = nums[0]: With only house 0, we rob it.
dp[1] = max(nums[0], nums[1]): With two houses, rob the richer one.

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

We can only rob one of the first two houses (they're adjacent). So we pick the one with more money. Note: this could also be derived from the recurrence with dp[-1] = 0 as a sentinel:

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

Include/Exclude Pattern

Complete Implementation — From O(n) Space to O(1)

Let's implement the House Robber solution in progressively optimized forms, following the same pattern we used for Fibonacci.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * House Robber — Basic Tabulation
 * 
 * Time: O(n)
 * Space: O(n) for the DP array
 */
function robTabulated(nums: number[]): number {
    const n = nums.length;
    
    // Edge cases
    if (n === 0) return 0;
    if (n === 1) return nums[0];
    
    // DP array: dp[i] = max money from houses 0..i
    const dp: number[] = new Array(n);
    
    // Base cases
    dp[0] = nums[0];
    dp[1] = Math.max(nums[0], nums[1]);
    
    // Fill the table
    for (let i = 2; i < n; i++) {
        // Choice: skip house i OR rob house i (which requires skipping i-1)
        dp[i] = Math.max(
            dp[i - 1],           // Skip house i: best up to i-1
            dp[i - 2] + nums[i]  // Rob house i: best up to i-2, plus nums[i]
        );
    }
    
    return dp[n - 1];
}
 
// Trace through example [2, 7, 9, 3, 1]:
// dp[0] = 2
// dp[1] = max(2, 7) = 7
// dp[2] = max(7, 2+9) = max(7, 11) = 11
// dp[3] = max(11, 7+3) = max(11, 10) = 11
// dp[4] = max(11, 11+1) = max(11, 12) = 12
// Result: 12

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
 * House Robber — Space-Optimized
 * 
 * Observation: dp[i] only depends on dp[i-1] and dp[i-2].
 * We only need to track the last two values.
 * 
 * Time: O(n)
 * Space: O(1)
 */
function rob(nums: number[]): number {
    const n = nums.length;
    
    if (n === 0) return 0;
    if (n === 1) return nums[0];
    
    // prev2 = dp[i-2], prev1 = dp[i-1]
    let prev2 = nums[0];
    let prev1 = Math.max(nums[0], nums[1]);
    
    for (let i = 2; i < n; i++) {
        const current = Math.max(prev1, prev2 + nums[i]);
        prev2 = prev1;
        prev1 = current;
    }
    
    return prev1;
}
 
// Alternative formulation (arguably cleaner)
function robAlt(nums: number[]): number {
    let robbed = 0;    // Max money if we robbed the previous house
    let skipped = 0;   // Max money if we skipped the previous house
    
    for (const money of nums) {
        // If we rob this house, we must have skipped the previous
        const newRobbed = skipped + money;
        // If we skip this house, we take the best of having robbed or skipped previous
        const newSkipped = Math.max(robbed, skipped);
        
        robbed = newRobbed;
        skipped = newSkipped;
    }
    
    return Math.max(robbed, skipped);
}
 
console.log(rob([2, 7, 9, 3, 1]));  // 12
console.log(rob([1, 2, 3, 1]));     // 4 (1 + 3)
console.log(rob([2, 1, 1, 2]));     // 4 (2 + 2)

State Transition View

•State: dp[i] = best from 0..i
•Transition: max(skip, include)
•Track: Last two dp values
•Natural for: Finding optimal value

Robbed/Skipped View

•State: (robbed, skipped) at each step
•Transition: newRob = skip+val, newSkip = max(rob,skip)
•Track: Two explicit states
•Natural for: Understanding decisions

Two Equivalent Formulations

Which Houses Did We Rob? Path Reconstruction

Often we need to know not just the maximum value, but which elements we selected. For House Robber, this means determining which houses were robbed in the optimal solution.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
/**
 * House Robber with Path Reconstruction
 * 
 * Returns both the maximum money and the indices of robbed houses.
 * 
 * Time: O(n)
 * Space: O(n) for storing the path
 */
function robWithPath(nums: number[]): { maxMoney: number; robbedHouses: number[] } {
    const n = nums.length;
    
    if (n === 0) return { maxMoney: 0, robbedHouses: [] };
    if (n === 1) return { maxMoney: nums[0], robbedHouses: [0] };
    
    // DP table
    const dp: number[] = new Array(n);
    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]);
    }
    
    // Backtrack to find which houses were robbed
    const robbedHouses: number[] = [];
    let i = n - 1;
    
    while (i >= 0) {
        if (i === 0) {
            // At house 0, we always include it if we reach here
            robbedHouses.push(0);
            break;
        } else if (i === 1) {
            // At houses 0-1, we pick the larger one
            robbedHouses.push(nums[1] > nums[0] ? 1 : 0);
            break;
        } else if (dp[i] === dp[i - 2] + nums[i]) {
            // We robbed house i
            robbedHouses.push(i);
            i -= 2;  // Must skip i-1, go to i-2
        } else {
            // We skipped house i
            i -= 1;
        }
    }
    
    robbedHouses.reverse();
    
    return {
        maxMoney: dp[n - 1],
        robbedHouses: robbedHouses,
    };
}
 
// Example
const result = robWithPath([2, 7, 9, 3, 1]);
console.log("Max money:", result.maxMoney);        // 12
console.log("Robbed houses:", result.robbedHouses); // [0, 2, 4]
 
// Verification: houses [0, 2, 4] have values [2, 9, 1] = 12 ✓
 
const result2 = robWithPath([1, 2, 3, 1]);
console.log("Max money:", result2.maxMoney);        // 4
console.log("Robbed houses:", result2.robbedHouses); // [1, 3] (values [2, 1] = 3... wait)
// Actually let's check: dp = [1, 2, 4, 4]
// Backtrack from i=3: dp[3]=4, dp[1]+nums[3] = 2+1=3, dp[2]=4, so skip 3
// i=2: dp[2]=4, dp[0]+nums[2] = 1+3=4, equal! So we robbed house 2.
// robbedHouses = [2], i becomes 0
// i=0: push 0, break
// robbedHouses = [0, 2], values [1, 3] = 4 ✓

Handling Ties in Backtracking

House Robber II — Circular Street

LeetCode 213 introduces a twist: the houses are arranged in a circle, so the first and last houses are adjacent.

Problem Statement:

All houses are arranged in a circle. The first house is the neighbor of the last one. Constraints remain: cannot rob adjacent houses. Find the maximum money.

The Key Insight:

Since houses 0 and n-1 are adjacent, we cannot rob both. This means valid robberies fall into two categories:

Don't rob house 0: Consider houses 1 through n-1 (linear problem)
Don't rob house n-1: Consider houses 0 through n-2 (linear problem)

The optimal solution is the maximum of these two linear subproblems!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/**
 * House Robber II — Circular Street
 * 
 * The houses form a circle, so house 0 and house n-1 are adjacent.
 * We cannot rob both the first and last house.
 * 
 * Strategy: Run two linear House Robber problems:
 * 1. Houses [0, n-2] (potentially rob first, definitely not last)
 * 2. Houses [1, n-1] (definitely not first, potentially rob last)
 * 
 * Time: O(n)
 * Space: O(1)
 */
function robCircular(nums: number[]): number {
    const n = nums.length;
    
    if (n === 0) return 0;
    if (n === 1) return nums[0];
    if (n === 2) return Math.max(nums[0], nums[1]);
    
    // Helper: solve linear House Robber for a subarray
    function robLinear(start: number, end: number): number {
        let prev2 = 0;
        let prev1 = 0;
        
        for (let i = start; i <= end; i++) {
            const current = Math.max(prev1, prev2 + nums[i]);
            prev2 = prev1;
            prev1 = current;
        }
        
        return prev1;
    }
    
    // Case 1: Possibly rob house 0, definitely skip house n-1
    const case1 = robLinear(0, n - 2);
    
    // Case 2: Definitely skip house 0, possibly rob house n-1
    const case2 = robLinear(1, n - 1);
    
    return Math.max(case1, case2);
}
 
// Examples
console.log(robCircular([2, 3, 2]));    // 3 (rob house 1)
console.log(robCircular([1, 2, 3, 1])); // 4 (rob houses 1 and 3, values 2+1... wait)
// Houses: [1, 2, 3, 1], circular so 0 and 3 are adjacent
// Case 1: houses [0,1,2] = [1,2,3] → rob 1 and 3? No, just [1,2,3], answer = max(1,2,1+3)=4
// Case 2: houses [1,2,3] = [2,3,1] → answer = max(2,3,2+1)=3
// max(4, 3) = 4 ← but this is 1+3 from [1,2,3] subset, which is houses 0 and 2
// Let me redo: houses 0 and 2 in original [1,2,3,1] have values 1 and 3, sum=4 ✓
 
console.log(robCircular([1, 2, 3]));    // 3 (can only rob house 1 for 2, or house 2 for 3... wait)
// Case 1: [0,1] = [1,2] → max(1,2) = 2
// Case 2: [1,2] = [2,3] → max(2,3) = 3
// Answer: 3 (rob house 2)

Reduce Circular to Linear

House Robber III — Tree Structure Preview

LeetCode 337 extends the problem to tree structures. While full tree DP is covered later, this variant demonstrates how the include/exclude pattern generalizes to trees.

Problem Statement:

Houses are arranged in a binary tree. The thief cannot rob two directly-connected houses. Find the maximum money.

The Approach:

For each tree node, we compute two values:

rob: Maximum money if we ROB this node
skip: Maximum money if we SKIP this node

The recurrence:

rob = node.value + skip(left) + skip(right) (if we rob here, we must skip children)
skip = max(rob(left), skip(left)) + max(rob(right), skip(right)) (if we skip, children can be either)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/**
 * House Robber III — Tree Structure
 * 
 * Binary tree where connected nodes cannot both be robbed.
 * 
 * For each node, compute [rob, skip]:
 * - rob: max money if we rob this node
 * - skip: max money if we skip this node
 * 
 * Time: O(n) — visit each node once
 * Space: O(h) — tree height for recursion stack
 */
 
interface TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
}
 
function robTree(root: TreeNode | null): number {
    // Returns [rob, skip] for the subtree rooted at node
    function dfs(node: TreeNode | null): [number, number] {
        if (node === null) return [0, 0];
        
        const [leftRob, leftSkip] = dfs(node.left);
        const [rightRob, rightSkip] = dfs(node.right);
        
        // If we rob this node, we must skip both children
        const rob = node.val + leftSkip + rightSkip;
        
        // If we skip this node, each child can be either robbed or skipped
        const skip = Math.max(leftRob, leftSkip) + Math.max(rightRob, rightSkip);
        
        return [rob, skip];
    }
    
    const [rob, skip] = dfs(root);
    return Math.max(rob, skip);
}
 
// Example tree:
//       3
//      / \
//     2   3
//      \   \
//       3   1
// 
// Nodes at level 0: [3]
// Nodes at level 1: [2, 3]  
// Nodes at level 2: [3, 1]
//
// Optimal: Rob 3 (root) + 3 (left-right grandchild) + 1 (right-right grandchild) = 7
// Or: Rob 2 + 3 (right child) = doesn't work, 2 and its parent 3 are adjacent
// Actually: Rob 3 (root's left's right child) + 3 (root) + 1 = 7
// Or: Skip root, rob 2's subtree (2+3=5) + rob right subtree (3+1=4... but 3 and 1 adjacent!)
// Right subtree: 3 with child 1, rob 3 = 3, skip 3 and rob 1 = 1, so max = 3
// Total if skip root: (skip 2, rob 3 from left = 3) + (rob 3 from right = 3) = no wait
// 
// Let me trace: 
// Node 1 (bottom right): [1, 0]
// Node 3 (right, parent of 1): rob=3+0=3, skip=max(1,0)=1, return [3, 1]
// Node 3 (bottom left of 2): [3, 0]
// Node 2: rob=2+0=2, skip=max(3,0)=3, return [2, 3]
// Node 3 (root): rob=3+3+1=7, skip=max(2,3)+max(3,1)=3+3=6, return [7, 6]
// Answer: max(7, 6) = 7 ✓

Tree DP Pattern

Related Problems — The Include/Exclude Family

The House Robber recurrence — dp[i] = max(dp[i-1], dp[i-2] + value[i]) — is a specific instance of the broader include/exclude pattern. Here are related problems that share this structure:

Include/Exclude Pattern in Various Problems
Problem	Including Element i	Excluding Element i	Constraint
House Robber	dp[i-2] + nums[i]	dp[i-1]	No adjacent elements
Delete & Earn	points[i-2] + total[i]	points[i-1]	Deleting x removes x±1
Best Time Buy/Sell Cooldown	sell[i-1] + prices[i]	cooldown	Cooldown after sell
Maximum Sum No 3 Consec	dp[i-2] + nums[i]	dp[i-1]	No three consecutive
Paint House	cost[i][c] + dp[i-1][c']	—	No same color adjacent

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
 * Delete and Earn (LeetCode 740)
 * 
 * You have an array nums. When you delete element x, you earn x points,
 * but you must also delete ALL occurrences of x-1 and x+1.
 * 
 * Insight: Group points by value, then it becomes House Robber!
 * If we "take" value v, we can't take v-1 or v+1 (adjacent values).
 * 
 * Time: O(n + max(nums))
 * Space: O(max(nums))
 */
function deleteAndEarn(nums: number[]): number {
    if (nums.length === 0) return 0;
    
    // Step 1: Count total points for each value
    const maxVal = Math.max(...nums);
    const points: number[] = new Array(maxVal + 1).fill(0);
    
    for (const num of nums) {
        points[num] += num;  // Each occurrence of num earns 'num' points
    }
    
    // Step 2: House Robber on the points array
    // points[i] = total points from taking all occurrences of value i
    // If we take value i, we can't take i-1 or i+1 (adjacent in value space)
    
    let prev2 = 0;  // dp[i-2]
    let prev1 = 0;  // dp[i-1]
    
    for (let i = 0; i <= maxVal; i++) {
        const current = Math.max(prev1, prev2 + points[i]);
        prev2 = prev1;
        prev1 = current;
    }
    
    return prev1;
}
 
console.log(deleteAndEarn([3, 4, 2]));       // 6: take 2 and 4 (sum 6)
console.log(deleteAndEarn([2, 2, 3, 3, 3, 4])); // 9: take 3s (sum 9)

Recognize the Pattern

Complexity Analysis and Comparison

Let's formally analyze the complexity of House Robber and compare it to alternative approaches.

Approach Comparison for House Robber
Approach	Time	Space	Practical Limit	Notes
Brute Force (all subsets)	O(2ⁿ)	O(n) stack	n ≈ 20	Exponentially explores all rob/skip choices
Brute Force + Pruning	O(~1.5ⁿ)	O(n) stack	n ≈ 30	Prune invalid (adjacent) states early
Memoization	O(n)	O(n)	n ≈ 10⁵	Cache on index; stack depth limits
Tabulation	O(n)	O(n)	n ≈ 10⁸	No stack; memory limits
Space-Optimized	O(n)	O(1)	n ≈ 10¹²	Only integer limits; essentially unlimited

Why O(n) subproblems?

In House Robber, the current best depends only on position i. The state is uni-dimensional: we only need to know "what's the best up to index i?" to compute "what's the best up to index i+1?"

This gives us n distinct subproblems, each solvable in O(1) time (just a max of two values), yielding O(n) total time.

Why O(1) space is possible?

General Principle: Lookback Determines Space

If a DP recurrence only looks back k steps (for constant k), space can be reduced to O(k). Fibonacci and Climbing Stairs: k=2 → O(1). Some problems have k=O(n), requiring O(n) space regardless.

Summary and Key Takeaways

The House Robber problem family teaches fundamental DP concepts that extend far beyond the specific problem:

Key Takeaways

•The include/exclude pattern: dp[i] = max(dp[i-1], dp[i-2] + value[i]) — choose to include element i (forcing exclusion of i-1) or exclude i.
•No-adjacent constraint: When elements conflict with neighbors, the recurrence naturally looks back two positions.
•Space optimization: Lookback of 2 means O(1) space is achievable with two variables.
•Circular extension: Break the circle by solving two linear subproblems that avoid the first-last conflict.
•Tree extension: Maintain (rob, skip) state pairs; children's skip allows parent's rob.
•Pattern recognition: Many problems (Delete & Earn, stock trading with cooldown) are House Robber with different wording.
•Path reconstruction: Track decisions to recover which elements were selected in the optimal solution.

Page Complete