We have a row of houses, each with some amount of money. We want to maximize the total money we collect, but we cannot rob two houses that are next to each other. So if we rob house i, we must skip house i+1 (and house i-1).

This is not as simple as "take every other house." Consider [2, 1, 1, 100]. If you greedily take house 0 and house 2 (skipping odd indices), you get 2 + 1 = 3. But the optimal is house 0 and house 3, giving 2 + 100 = 102. The decision of whether to rob a house depends on decisions made for earlier houses.

At each house, you have exactly two choices. Rob it, which means adding its value to the best you could do up to two houses back, or skip it, which means carrying forward the best you could do up to the previous house. Picking the larger of these two options at every house is what this problem reduces to, and that "take or skip with a neighbor constraint" structure is a dynamic programming setup.

Key Constraints:

Intuition

We can express the answer through a recursive decision at each house: rob it or skip it.

If we rob house i, we earn nums[i] and then solve the subproblem for houses 0 through i-2, since house i-1 must be skipped. If we skip house i, we solve the subproblem for houses 0 through i-1. The answer for house i is the larger of these two results.

This recursion models the problem directly, but it is slow because the same subproblem gets solved repeatedly. Computing the answer for house 5 requires the answers for houses 3 and 4, and house 4 in turn requires house 3. Because these subproblems overlap, the recursion tree branches into roughly two children at every level, so the number of calls grows exponentially.

Algorithm

Example Walkthrough

Code

The recursion recomputes the same subproblems many times. Storing the result of each rob(i) the first time it is computed removes that wasted work, which is the next approach.

Intuition

The brute force recursion does too much redundant work, which we fix by caching results. The first time we compute rob(i), we store the answer. Every later call to rob(i) returns the cached value immediately.

This technique is called memoization. Each subproblem rob(0) through rob(n-1) is now solved exactly once, and each does O(1) work: one comparison and one addition. The total work drops from O(2^n) to O(n).

Algorithm

Example Walkthrough

Code

This uses O(n) space for the memo array plus O(n) for the recursion stack. Since rob(i) depends only on rob(i-1) and rob(i-2), the answers can be filled in iteratively from left to right, which removes the recursion entirely.

Intuition

Instead of starting from the last house and recursing backward, we reverse the direction. Start from the first house and work forward. For each house i, compute the best we can do considering houses 0 through i. The recurrence is the same: dp[i] = max(dp[i-1], nums[i] + dp[i-2]). Filling the table iteratively removes the recursion overhead and makes the computation order explicit.

This bottom-up form is easy to analyze and carries no risk of stack overflow on a long input, since there are no recursive calls at all.

Algorithm

Example Walkthrough

Code

This allocates an array of size n, but at any step only the last two values are read. The dp array can be replaced with two variables, which is the final approach.

Intuition

The recurrence dp[i] = max(dp[i-1], nums[i] + dp[i-2]) reads only two past values: the result one step back and the result two steps back. Once we move past house i, the value at dp[i-2] is never read again. So instead of the full dp array, we keep two variables: prev1 for the best up to the previous house and prev2 for the best up to two houses back.

At each house we compute the new best, then shift the variables so the old prev1 becomes the new prev2 and the newly computed value becomes prev1. This produces the same sequence of values as the tabulation array while bringing space from O(n) down to O(1).

Algorithm

Example Walkthrough

Code