The Matrix: Mastering House Robber DP from Zero to Hero

The Quest Begins (The “Why”)

I still remember the first time I saw a coding interview question that asked me to pick the maximum amount of money you can rob from a line of houses without hitting two adjacent ones. My brain instantly went into panic mode: “Do I try every subset? That’s 2ⁿ possibilities – impossible for n = 100!” I spent an hour scribbling brute‑force loops, only to watch my solution time out on the smallest test case. It felt like I was stuck in a boss fight where the boss kept respawning stronger each time I swung my sword.

The frustration turned into curiosity: Why does this problem feel impossible at first glance, yet there’s a clean, linear‑time solution lurking underneath? That’s the moment I decided to treat DP not as a scary acronym but as a map‑making tool for the interview dungeon.

The Revelation (The Insight)

The House Robber problem is a textbook example of optimal substructure and overlapping subproblems – the two pillars that make dynamic programming tick.

Optimal substructure: The best loot you can get from the first i houses depends only on the best loot from the first i‑1 houses or the first i‑2 houses plus the value of house i. Why? Because if you rob house i, you must skip house i‑1; if you don’t rob it, you’re free to consider house i‑1. No other choice matters.

Overlapping subproblems: When you compute the answer for house i, you’ll need the answer for house i‑1 and i‑2 again and again as you move forward. Without memoization you’d recompute the same sub‑answers exponentially many times – exactly what my brute‑force attempt was doing.

So the “treasure” is realizing we only need to keep two numbers: the best loot up to the previous house (prev) and the best loot up to the house before that (prev2). At each step we compute

curr = max(prev, prev2 + value[i])

and then shift the window forward. No arrays, no recursion, just a constant‑size state that we update in O(1) per house.

The math is simple, but the why is powerful: we’re not enumerating subsets; we’re propagating the optimal decision forward, guaranteeing that when we reach the end we’ve already considered every feasible combination exactly once.

Wielding the Power (Code & Examples)

The Struggle (Before)

def rob_brute(nums):
    # tries every subset – exponential, times out quickly
    from itertools import combinations
    best = 0
    for r in range(len(nums)+1):
        for combo in combinations(range(len(nums)), r):
            if all(abs(combo[i]-combo[i+1])>1 for i in range(len(combo)-1)):
                best = max(best, sum(nums[i] for i in combo))
    return best

Problems:

• O(2ⁿ) time, O(n) recursion depth if done recursively.
• Easy to miss the adjacency check, leading to wrong answers.
• Feels like you’re brute‑forcing a Sudoku puzzle with a hammer.

The Victory (After)

def rob(nums):
    """
    House Robber – O(n) time, O(1) space.
    prev   = best loot up to i-1
    prev2  = best loot up to i-2
    """
    prev2 = 0   # nothing taken yet
    prev  = 0   # best loot so far
    for money in nums:
        curr = max(prev, prev2 + money)   # either skip this house or rob it
        prev2, prev = prev, curr          # shift the window
    return prev

Why this works:

• At each house i, prev already holds the optimum for houses [0 … i-1].
• prev2 holds the optimum for houses [0 … i-2].
• If we rob house i, we must add its value to prev2 (since i-1 is off‑limits).
• If we skip it, we just keep prev.
• Taking the max gives the optimum for [0 … i].
• After the loop, prev is the answer for the whole street.

Common Traps (the “boss mechanics”)

1. Forgetting the shift – If you do prev = curr without updating prev2, you’ll lose the i‑2 state and start double‑counting adjacent houses.
2. Using an array when you don’t need it – dp = [0] * (len(nums)+1) works but wastes O(n) space; the two‑variable trick is the true “spell” for O(1) memory.

Real‑World Interview Flavors

1. LeetCode 198 – House Robber (the classic).
   
   Input: [2,7,9,3,1] → Output: 12 (rob houses 0, 2, 4).

2. Variation – House Robber II (houses in a circle).
   
   You run the same rob function twice: once excluding the first house, once excluding the last house, and take the max. The core DP stays identical, proving how reusable the pattern is.

Both problems appear regularly in FAANG‑style screens, and once you internalize the two‑state update, you’ll solve them in under five minutes.

Why This New Power Matters

Mastering this tiny DP pattern does more than let you pass a single interview question. It teaches you to spot the recursive relationship hidden in a seemingly combinatorial mess and to compress that relationship into a constant‑size state. That skill transfers to:

• Stock‑trading problems (buy/sell with cooldown).
• Text justification (minimize raggedness).
• Sequence alignment (the backbone of bioinformatics).

In short, you’ve added a reliable spell to your developer grimoire: “When you see a choice that depends only on the last two decisions, think DP with two variables.”

You’ll start recognizing these patterns in the wild, refactoring messy recursive solutions into sleek iterative loops, and watching your runtime drop from exponential to linear—all while feeling like you’ve just leveled up in a role‑playing game where the boss was “exponential time” and your new spell is “DP‑two‑state”.

---

Your Turn

Grab a piece of paper (or your favorite IDE) and try the House Robber II variant on your own. Post your solution or a question in the comments—let’s keep the quest going together! 🚀