House Robber: Optimal Non-Adjacent Sum via DP

Problem Summary

You’re given an array nums where each element is the cash in a house on a street. Robbing two adjacent houses triggers an alarm, so you must choose a subset of houses with no two neighbors to maximize the total amount taken. Return that maximum sum.

Constraints keep the input small and friendly to linear solutions. Length is in [1, 100], and each amount is in [0, 400]. The overall sum fits easily in a 32-bit integer. The structure is classic dynamic programming on a line with an adjacency restriction.

My Approach

This is the textbook “choose or skip” dynamic programming pattern on a path. At every house i, you have two options.

• Skip house i. Then the best you can do up to i is exactly the best up to i−1.
• Rob house i. Then you cannot rob i−1, so you add nums[i] to the best up to i−2.

That produces a clean recurrence.

Let dp[i] mean the maximum money you can rob from the first i+1 houses, i.e., from indices [0..i]. The transition is:

• Base cases
  • dp[0] = nums[0]
  • dp[1] = max(nums[0], nums[1])
• For i ≥ 2
  • dp[i] = max(dp[i−1], dp[i−2] + nums[i])

The final answer is dp[n−1]. This yields O(n) time and O(n) space. For production code, I’d reduce space to O(1) by keeping only the last two states, since each transition only references dp[i−1] and dp[i−2]. With n ≤ 100 the full array is fine and improves readability for many.

Why this approach? It encodes the only real dependency imposed by the no-adjacent constraint. Each new decision depends only on the two prior states, which is exactly the kind of locality dynamic programming thrives on.

Why This Works

The correctness argument is a straightforward induction on the index i.

• For i = 0, the best you can do is rob the only house, so dp[0] = nums[0].
• For i = 1, you can’t rob both houses due to adjacency. The best is max(nums[0], nums[1]).

Assume for all positions j < i that dp[j] holds the correct maximum for houses [0..j]. Consider dp[i]. Any optimal solution either uses house i or it doesn’t.

• If it doesn’t use i, then the solution is exactly an optimal solution on [0..i−1], which has value dp[i−1] by the induction hypothesis.
• If it does use i, then it cannot use i−1, so it must pair nums[i] with an optimal solution on [0..i−2], which is dp[i−2] by the induction hypothesis. The value is dp[i−2] + nums[i].

An optimal solution must be one of these two, hence dp[i] is the max of those two values. This proves dp[i] gives the optimal value for [0..i]. By induction, dp[n−1] is optimal for the full array.

Another way to view it is as a maximum-weight independent set on a path graph. Each house is a vertex with weight nums[i], and edges connect adjacent vertices. On a path, the maximum-weight independent set admits a simple right-to-left or left-to-right DP with exactly these transitions.

Code Walkthrough

Here’s the provided C++ implementation, already annotated with comments. It uses an O(n) DP array and handles the small base cases explicitly.

C++
Copy
1
class Solution {
2
public:
3
    int rob(vector<int>& nums) {
4
        // Check if there is only one house
5
        if (nums.size() == 1) return nums[0];
6
        // Create a DP array to store the maximum money that can be robbed up to each house
7
        vector<int> dp(nums.size(), 0);
8
        // Base case: maximum money for the first house
9
        dp[0] = nums[0];
10
        // Base case: maximum money for the first two houses
11
        dp[1] = max(nums[0], nums[1]);
12
        // Initialize the answer with the maximum of the first two houses
13
        int ans = max(dp[0], dp[1]);
14
        // Iterate through the houses starting from the third one
15
        for (int i = 2; i < nums.size(); ++i) {
16
            // Choose the max between skipping the current house or robbing it (adding current house value to the max before the last house)
17
            dp[i] = max(dp[i-1], dp[i-2] + nums[i]);
18
            // Update the answer with the maximum money robbed so far
19
            ans = max(ans, dp[i]);
20
        }
21
        return ans; // Return the maximum amount of money that can be robbed
22
    }
23
};

Key points to notice when reading the code.

• Early return for a single house. With only one house, you have to take it or leave it. Taking it is optimal when non-negative values are allowed, which they are here.
• dp array meaning. dp[i] holds the optimal value for [0..i]. This is the most convenient interpretation because it keeps the recurrence simple.
• Base cases dp[0] and dp[1]. They match the reasoning above. Many bugs in similar problems happen when these aren’t handled precisely.
• Iteration starts at i = 2. The recurrence uses dp[i−1] and dp[i−2], so those must be precomputed.
• The extra ans variable stores the current max. It’s redundant here because dp[i] is non-decreasing for non-negative nums, so ans will end up equal to dp.back(). If you prefer minimal state, you can return dp.back() directly.

Complexity.

• Time: O(n) since each house is processed once.
• Space: O(n) for the dp array. This can be improved to O(1) as shown below.

A compact O(1) space version you might use in practice.

C++
Copy
1
int rob(vector<int>& nums) {
2
    if (nums.size() == 1) return nums[0];
3
    int prev2 = nums[0];                 // dp[i-2]
4
    int prev1 = max(nums[0], nums[1]);   // dp[i-1]
5
    for (int i = 2; i < nums.size(); ++i) {
6
        int cur = max(prev1, prev2 + nums[i]);
7
        prev2 = prev1;
8
        prev1 = cur;
9
    }
10
    return prev1;
11
}

The variables prev1 and prev2 play the role of dp[i−1] and dp[i−2]. That’s all the state you need because the transition only references those two.

Alternative Approaches

Different formulations lead to the same recurrence. They’re useful in different contexts.

• Space-optimized iterative DP (O(n) time, O(1) space)

  • When to pick it: Memory is tight or n is large. It’s just as readable once you’re familiar with the pattern and avoids allocating an array. For n up to 100 both are fine, but I still prefer the O(1) variant for its clarity and minimal state.

• Top-down recursion with memoization (O(n) time, O(n) space)

  • When to pick it: You want a direct expression of the choice structure, or you’re prototyping quickly. Define f(i) as the answer for [0..i]. Then f(i) = max(f(i−1), f(i−2) + nums[i]) with memoization. It’s easy to write and mirrors the problem statement. Avoid it if recursion depth is a concern, though with n ≤ 100 that’s not an issue.

• Graph viewpoint: maximum-weight independent set on a path (O(n) time)

  • When to pick it: You’re connecting to graph theory or generalizing to other graph classes. This framing explains why the DP is so clean: paths are acyclic and have small treewidth, so two-state DP suffices. On trees, you get a related two-state DP per node (see House Robber III in Further Thinking).

• Greedy

  • When to pick it: Never here. Local choices such as “always take the larger of the next two houses” fail on inputs like [2, 1, 4]. The greedy pick of 2 blocks 1 but then forces 4, yielding 6, which happens to be optimal here, but you can make counterexamples where greedy loses. Dynamic programming is the right tool.

Pitfalls and Edge Cases

A few issues can cause wrong answers or crashes if you’re not careful.

• Arrays of length 1

  • Always handle this explicitly. Accessing nums[1] or dp[1] will be out of bounds.

• Arrays of length 2

  • The base case dp[1] = max(nums[0], nums[1]) ensures you don’t add them. Forgetting this leads to robbing both.

• Off-by-one in the loop

  • The loop should start at i = 2 and go through i = n−1. Starting at i = 1 or using the wrong bound will either skip transitions or access dp[−1].

• Misinterpreting dp’s meaning

  • Some define dp[i] as “best if you must rob i,” others as “best up to i.” Both can work, but the transition and base cases change. Stick to one definition consistently. The code here uses “best up to i.”

• Overflow concerns in other settings

  • With the given constraints, the maximum sum is at most 100 × 400 = 40,000, which fits in a 32-bit int. If the ranges were larger, upgrade to 64-bit integers.

• Negative values (not in this problem)

  • If nums could be negative, the standard recurrence still works, but some base cases may prefer skipping. For example, dp[0] would be max(0, nums[0]) if skipping is allowed. Here all values are non-negative, so always taking a single house is safe.

• Redundant tracking of ans

  • dp[i] is non-decreasing with non-negative inputs. The extra ans variable is not needed; returning dp.back() is equivalent. If you modify the problem to allow negative values or different constraints, dp may not be monotonic, and then tracking a separate maximum can matter.

Further Thinking

Problems and variations that build similar muscles.

1. House Robber II (circular street)

• Each house sits on a ring, so the first and last are adjacent. Hint: solve two linear cases and take the max: houses [0..n−2] and houses [1..n−1]. Same recurrence, just avoid including both ends.

1. House Robber III (binary tree)

• Houses are nodes in a tree, adjacency means parent-child. Hint: for each node, compute two values: include it (so exclude children), or exclude it (children free to choose). Post-order traversal with O(n) time.

1. Delete and Earn

• Picking value v deletes neighbors v−1 and v+1. Hint: bucket values by number, convert to a linear array by value, then run the House Robber DP on totals per value.

1. Maximum sum of non-adjacent elements

• Same problem under a different name. Hint: identical recurrence, just different framing.

1. Paint Fence or Paint House with constraints

• While not identical, they feature local choices with constraints that block neighbors or colors. Hint: per-position DP with a bounded dependency window, often two or three previous states.

1. Largest independent set on a path or tree

• General graph perspective. Hint: on a path you get the same 2-state DP; on trees you use include/exclude states and combine children.

1. Stock trading with cooldown

• After selling, you must wait a day. Hint: define states (holding, not holding, cooldown) and transition day by day. Similar flavor of “can’t take adjacent actions.”

1. Maximum sum subsequence with gap k

• Pick numbers with at least k elements apart. Hint: generalize the recurrence to use dp[i−k−1] when taking index i.

These variations all reinforce the mental model: when a choice at position i invalidates nearby positions, dynamic programming across a short dependency window is usually the right tool.

Example 1

• input: nums = [1,2,3,1]
• output: 4
• explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3). Total amount you can rob = 1 + 3 = 4.

<strong class="

Example 2

• input: nums = [2,7,9,3,1]
• output: 12
• explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1). Total amount you can rob = 2 + 9 + 1 = 12.