Dynamic Programming — House Robber

↗ LeetCode: House Robber · Medium · pattern chapter →

Asked atMetaAmazonGoogleMicrosoftLinkedInBloomberg

Given nums[i] = value at house i, return the max total value you can rob given you can't rob two adjacent houses.

Example 1 — [2,7,9,3,1] → 12 (rob 2 + 9 + 1) Example 2 — [2,1,1,2] → 4 (rob 2 + 2)

Constraints — 1 ≤ n ≤ 100; 0 ≤ nums[i] ≤ 400. Brute recursion tries include-or-skip at each house — O(2ⁿ) = 10³⁰ ops at n=100. Even at 10⁹ ops/sec that's ~10¹³ years — 700× the age of the universe. DP with 2-variable rolling state is O(n) = 100 ops = trivial.

Progressive Hints

Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.

---

⏱️Interview timer00:00

Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.

Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.

Approach 1 — Brute force recursion

Intuition. At each house: either rob it (skip next) or skip it. Return the max.

int robBrute(int[] a) { return rec(a, 0); }
int rec(int[] a, int i) {
    if (i >= a.length) return 0;
    int rob = a[i] + rec(a, i + 2);
    int skip = rec(a, i + 1);
    return Math.max(rob, skip);
}

Complexity — Time O(2ⁿ); Space O(n) recursion. TLE at n=100.

---

Approach 2 — Memoized recursion (top-down DP)

Insight from brute. The recursion revisits rec(a, i) exponentially many times. Cache it.

int robMemo(int[] a) {
    Integer[] memo = new Integer[a.length];
    return rec(a, 0, memo);
}
int rec(int[] a, int i, Integer[] memo) {
    if (i >= a.length) return 0;
    if (memo[i] != null) return memo[i];
    return memo[i] = Math.max(a[i] + rec(a, i + 2, memo), rec(a, i + 1, memo));
}

Complexity — Time O(n); Space O(n).

---

Approach 3 — Bottom-up DP (tabulation)

Insight from memo. Compute dp[i] = max value from i..n-1 iteratively.

int robTable(int[] a) {
    int n = a.length;
    int[] dp = new int[n + 2];
    for (int i = n - 1; i >= 0; i--)
        dp[i] = Math.max(a[i] + dp[i + 2], dp[i + 1]);
    return dp[0];
}

Complexity — Time O(n); Space O(n).

---

Approach 4 — Rolling variables (O(1) space)

Insight from tabulation. We only ever read dp[i+1] and dp[i+2] — two variables suffice.

int rob(int[] a) {
    int prev2 = 0, prev1 = 0;
    for (int x : a) {
        int cur = Math.max(prev1, prev2 + x);
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

Execution Trace

O(1)-space DP — nums=[2,7,9,3,1]

Step 1 / 5max(0, 0+2)=2

Complexity — Time O(n); Space O(1). Optimal.

---

Try it yourself

Complexity summary

Approach	Time	Space
Brute recursion	O(2ⁿ)	O(n)
Memoized	O(n)	O(n)
Tabulated	O(n)	O(n)
Rolling variables	O(n)	O(1)

When to use which

• Cold interview → walk brute → memo → table → rolled. This ladder shows the full DP thought process.
• Interviewer probes "why rolled?" → we only need dp[i-1] and dp[i-2].

✨AI Study CompanionBeta

Related problems (same ladder applies)

• House Robber II — circle: run twice, exclude first vs exclude last
• Delete and Earn — bucket by value, then House Robber
• Paint House — 3-state variant
• Climbing Stairs — same recurrence shape (Fibonacci)

Was this page helpful?