Difficulty: Medium1-D Dynamic Programming

House Robber

Problem in Plain English

Given the cash in each house on a street, rob the largest total possible without ever robbing two adjacent houses.

Problem Statement

You are given an integer array nums where nums[i] is the money in house i. Robbing two adjacent houses in one night triggers the alarm.

Return the maximum money robbable with no two robbed houses adjacent. Every house may also be skipped, and all amounts are non-negative.

Constraints

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

Examples

Example 1

Input: nums = [1, 2, 3, 1]
Output: 4

Rob house 1 (money 1) and house 3 (money 3) for a total of 4.

Example 2

Input: nums = [2, 7, 9, 3, 1]
Output: 12

Rob houses 1, 3, and 5 for 2 + 9 + 1 = 12.

Example 3

Input: nums = [0]
Output: 0

The only house contains no money. Robbing it or skipping it both give 0, so the answer is 0.

Example 4

Input: nums = [2, 1, 1, 2]
Output: 4

Take indices 0 and 3 for 4. They are not adjacent on a line; fixed even-index and odd-index plans each give only 3, so choosing a parity is not sufficient.

Intuition

The largest individual house does not decide the best night: neighbouring choices affect what remains available. In Example 1, [1, 2, 3, 1], taking values 1 and 3 gives 4, beating the middle value 2. At each position compare skipping this house with taking it plus the best plan that excludes its neighbour. Only the best totals through the previous two positions matter, so a whole table can be compressed into two running totals.

Approaches

Recursive Take Or Skip

Solution Details

Reveal Recursive Take Or Skip: intuition, complexity, and code

Intuition

Enumerate the two choices at the current house: skip it and continue one position later, or take it and continue two positions later. The jump makes the adjacency rule automatic. Returning the larger branch gives the best valid plan, but overlapping tails are recomputed because this version stores no answers.

Step-by-Step Logic

Define dfs(i) as the best loot from index i onward and start at index 0. Return 0 whenever i is outside the array.
Evaluate the skip branch at i + 1 and the take branch at i + 2, adding nums[i] only to the take branch. In Example 1, index 0 compares dfs(1) against 1 + dfs(2).
Return the larger branch at every call, without caching. For Example 1, dfs(2) is 3 and dfs(1) is 3; both appearances of dfs(2) are evaluated separately.
The root returns the best whole-street total. Example 1 returns max(3, 1 + 3) = 4.

Why It Works

Let dfs(i) mean the maximum loot available from index i through the end of the street. When i >= n, no houses remain and the answer is 0. Every valid plan either skips i, giving dfs(i + 1), or takes i and must skip its neighbour, giving nums[i] + dfs(i + 2). These branches exhaust all valid choices, and each combines only nonadjacent houses. By induction on the remaining street length, taking their maximum is optimal. Calling dfs(0) applies the argument to the entire street.

Dry Run

Recursive Take Or Skip: variable states at each step
call ID (assigned on entry)	case	call returning (return order)	branch totals	returned best
5	whole street	dfs(4)	empty range	0
6	whole street	dfs(5)	empty range	0
4	whole street	dfs(3)	skip 0; take 1 + 0 = 1	1
7	whole street	dfs(4)	empty range	0
3	whole street	dfs(2)	skip 1; take 3 + 0 = 3	3
9	whole street	dfs(4)	empty range	0
10	whole street	dfs(5)	empty range	0
8	whole street	dfs(3)	skip 0; take 1 + 0 = 1	1
2	whole street	dfs(1)	skip 3; take 2 + 1 = 3	3
13	whole street	dfs(4)	empty range	0
14	whole street	dfs(5)	empty range	0
12	whole street	dfs(3)	skip 0; take 1 + 0 = 1	1
15	whole street	dfs(4)	empty range	0
11	whole street	dfs(2)	skip 1; take 3 + 0 = 3	3
1	whole street	dfs(0)	skip 3; take 1 + 3 = 4	4
answer	whole street	root returned	return	4

Complexity Analysis

Time Complexity

O(2^n)

Space Complexity

O(n)

Let n be the number of houses. The call count satisfies a Fibonacci-like recurrence because the branches advance by one and two, so O(2^n) is a valid loose exponential upper bound, not an exact doubling per house. At most O(n) frames are simultaneously live. Each frame stores a few scalars; no slices, result arrays or memo tables are allocated, and the input is unchanged. This uncached approach is for teaching and is impractical near n = 100.

Code

Solution.java

1class Solution {2    public int rob(int[] nums) {3        return dfs(nums, 0);4    }5
6    private int dfs(int[] nums, int i) {7        if (i >= nums.length) {8            return 0;9        }10        int skip = dfs(nums, i + 1);11        // Taking this house skips its adjacent successor.12        int take = nums[i] + dfs(nums, i + 2);13        return Math.max(skip, take);14    }15}

Hints

Hint 1

At every house there are exactly two finished plans to extend: the best that skips this house and the best that robs it.

Hint 2

Robbing house i requires combining its money with the best total through i - 2. Skipping it keeps the best through i - 1; compare those two totals.

Hint 3

Only best(i - 1) and best(i - 2) feed the next house, so two rolling variables replace the array.

Edge Cases

A single house returns its own value with no adjacency to check.
All zeros return 0; skipping everything stays valid and optimal.
Two houses return the richer one, exercising both the rob-first and rob-second paths.

Common Mistakes and Interview Tips

Robbing every other house by fixed parity fails inputs like [2, 1, 1, 2], where the optimum mixes parities for 4.
Writing nums[i] + prev1 for the rob branch reuses the previous house and can rob neighbours.
Updating prev2 after overwriting prev1 feeds the new value into both slots; shift with a temporary.
The two rolling variables are best prefix totals, not amounts in the previous two houses. In an interview, state that invariant before compressing a DP table.

Key Takeaway

Take-or-skip optimisation over a line, where taking blocks the neighbour, is a two-state rolling recurrence: the best ending before contains everything the future needs.