101.House Robber

MediumBlind 751-D Dynamic Programming · 3/12

Problem

Houses along a street each hold some money, given as nums[i]. You want to rob as much as possible, but two adjacent houses cannot both be robbed — their alarms are linked.

Return the maximum amount of money you can rob without robbing two neighbouring houses.

Examples

Input:  nums = [1, 2, 3, 1]
Output: 4
Explanation: Rob house 0 (1) and house 2 (3): 1 + 3 = 4.

Input:  nums = [2, 7, 9, 3, 1]
Output: 12
Explanation: Rob houses 0, 2 and 4: 2 + 9 + 1 = 12.

Input:  nums = [2, 1, 1, 2]
Output: 4
Explanation: Rob houses 0 and 3 — skipping two in a row is allowed.

Constraints

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

💡 Key Insight

At each house i there are only two choices: skip it (keep the best answer for the first i - 1 houses) or rob it (add nums[i] to the best answer for the first i - 2 houses). So best(i) = max(best(i - 1), nums[i] + best(i - 2)). The state only looks back two positions, so the whole DP collapses into two rolling variables.

Recursion (Brute Force)

TimeO(2ⁿ)SpaceO(n)

Intuition

Walk from the last house backwards. For house i, either rob it (then house i - 1 is off-limits, continue at i - 2) or skip it (continue at i - 1). Return the better of the two.

Recurrence: f(i) = max(f(i - 1), nums[i] + f(i - 2)), with f(i) = 0 for i < 0.

Algorithm

dfs(i): if i < 0 return 0.
Return max(dfs(i - 1), nums[i] + dfs(i - 2)).
Answer is dfs(n - 1).

Visualization

nums = [2, 7, 9, 3]. f(1) is computed twice and f(0) three times.

flowchart TD
    A["f(3)"] -->|"skip 3"| B["f(2)"]
    A -->|"rob 3"| C["3 + f(1)"]
    B -->|"skip 2"| D["f(1)"]
    B -->|"rob 2"| E["9 + f(0)"]
    C -->|"skip 1"| F["f(0)"]
    C -->|"rob 1"| G["7 + f(-1)"]
    D -->|"skip 1"| H["f(0) = 2"]
    D -->|"rob 1"| I["7 + f(-1) = 7"]

f(0) = 2, f(1) = 7, f(2) = max(7, 9 + 2) = 11, f(3) = max(11, 3 + 7) = 11.

Code

java

class Solution {
    public int rob(int[] nums) {
        return dfs(nums, nums.length - 1);
    }

    // best loot from houses 0..i
    private int dfs(int[] nums, int i) {
        if (i < 0) {
            return 0;
        }
        int skip = dfs(nums, i - 1);
        int take = nums[i] + dfs(nums, i - 2); // neighbour i - 1 is forbidden
        return Math.max(skip, take);
    }
}

Complexity

Time: O(2ⁿ) — two branches per house.
Space: O(n) — recursion depth.

Top-Down Memoization

TimeO(n)SpaceO(n)

Intuition

The answer for a prefix 0..i never changes, so store f(i) in memo[i]. Each of the n prefixes is computed once.

Algorithm

memo of size n, filled with -1 (0 is a legal answer).
dfs(i): i < 0 → 0; return memo[i] if set.
Otherwise compute max(dfs(i - 1), nums[i] + dfs(i - 2)), store, return.

Dry Run

nums = [2, 7, 9, 3, 1]
memo[0] = 2
memo[1] = max(2, 7 + 0)   = 7
memo[2] = max(7, 9 + 2)   = 11
memo[3] = max(11, 3 + 7)  = 11
memo[4] = max(11, 1 + 11) = 12   → answer 12

Code

java

import java.util.Arrays;

class Solution {
    private int[] memo;

    public int rob(int[] nums) {
        memo = new int[nums.length];
        Arrays.fill(memo, -1);
        return dfs(nums, nums.length - 1);
    }

    private int dfs(int[] nums, int i) {
        if (i < 0) {
            return 0;
        }
        if (memo[i] != -1) {
            return memo[i];
        }
        memo[i] = Math.max(dfs(nums, i - 1), nums[i] + dfs(nums, i - 2));
        return memo[i];
    }
}

Complexity

Time: O(n) — each index solved once.
Space: O(n) — memo and recursion stack.

Bottom-Up Tabulation

TimeO(n)SpaceO(n)

Intuition

Let dp[i] be the best loot from the first i houses (dp[0] = 0, no houses). Shifting the index by one removes the special case for i - 2 < 0.

Algorithm

dp of size n + 1; dp[0] = 0, dp[1] = nums[0].
For i = 2..n: dp[i] = max(dp[i - 1], nums[i - 1] + dp[i - 2]).
Return dp[n].

Dry Run

nums = [2, 7, 9, 3, 1]:

i	0	1	2	3	4	5
house robbed?	–	2	7	9	3	1
dp[i]	0	2	7	11	11	12

dp[5] = max(dp[4], 1 + dp[3]) = max(11, 12) = 12.

Code

java

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n + 1]; // dp[i] = best from the first i houses
        dp[1] = nums[0];
        for (int i = 2; i <= n; i++) {
            dp[i] = Math.max(dp[i - 1], nums[i - 1] + dp[i - 2]);
        }
        return dp[n];
    }
}

Complexity

Time: O(n) — one pass.
Space: O(n) — dp array.

Space-Optimized DPOptimal

TimeO(n)SpaceO(1)

Intuition

Only the last two dp values are read. Keep rob1 = dp[i - 2] and rob2 = dp[i - 1]; for each house compute the new best and slide the window.

Algorithm

rob1 = 0, rob2 = 0.
For each num in nums:
- newRob = max(rob2, num + rob1)
- rob1 = rob2, rob2 = newRob
Return rob2.

Dry Run

flowchart LR
    A["start<br/>rob1=0, rob2=0"] -->|"num=2"| B["max(0, 2+0)=2<br/>rob1=0, rob2=2"]
    B -->|"num=7"| C["max(2, 7+0)=7<br/>rob1=2, rob2=7"]
    C -->|"num=9"| D["max(7, 9+2)=11<br/>rob1=7, rob2=11"]
    D -->|"num=3"| E["max(11, 3+7)=11<br/>rob1=11, rob2=11"]
    E -->|"num=1"| F["max(11, 1+11)=12<br/>rob1=11, rob2=12"]
    F --> G["return 12"]

Code

java

class Solution {
    public int rob(int[] nums) {
        int rob1 = 0; // best up to house i - 2
        int rob2 = 0; // best up to house i - 1
        for (int num : nums) {
            int newRob = Math.max(rob2, num + rob1); // skip vs. rob this house
            rob1 = rob2;
            rob2 = newRob;
        }
        return rob2;
    }
}

Complexity

Time: O(n) — single pass.
Space: O(1) — two integers.

Complexity Comparison

Approach	Time	Space
Recursion (Brute Force)	O(2ⁿ)	O(n)
Top-Down Memoization	O(n)	O(n)
Bottom-Up Tabulation	O(n)	O(n)
Space-Optimized DP	O(n)	O(1)

Common Pitfalls

Greedily taking all even or all odd indices — [2, 1, 1, 2] needs houses 0 and 3 (answer 4), which neither parity gives.
Using 0 as the memo sentinel: houses can hold 0, so many prefix answers are legitimately 0.
Indexing nums[1] or dp[2] when n == 1 — handle the single-house case.
Updating rob1 before computing newRob — compute the new value first, then shift.