House Robber: The DP Heist (Ocean's Eleven Style)

The Quest Begins (The "Why")

I still remember the first time I saw a dynamic programming problem on a whiteboard during an interview. The interviewer slid a simple array of numbers toward me and said, “Pick houses to rob, but you can’t hit two next to each other. Maximize the cash.” My brain went into overdrive. I started sketching recursion trees, trying every combination, and before I knew it I was staring at an exponential nightmare—O(2ⁿ)—and sweating like I’d just walked into a laser grid. I felt like I was trying to crack a vault with a toothpick.

Honestly, that frustration is why I dove deeper into DP. I wanted a repeatable way to turn those nasty overlapping subproblems into something linear, something I could actually explain without sounding like I’d memorized a spellbook. The House Robber problem turned out to be the perfect gateway. Once I grasped its core idea, a whole class of “pick‑or‑skip” challenges started to feel like Level 1 bosses instead of final‑form dragons.

The Revelation (The Insight)

So what’s the secret sauce? It boils down to two truths that feel obvious once you see them:

1. Optimal substructure – The best loot you can get from the first i houses only depends on the best loot from the first i‑1 houses and the first i‑2 houses.
   
   Why? Because if you rob house i, you must skip house i‑1. The best you can do then is the value of house i plus whatever you could snag from houses 0…i‑2. If you skip house i, you’re just carrying forward the best from houses 0…i‑1. The answer for i is the max of those two options.

2. Overlapping subproblems – The same sub‑answers (best loot for a prefix) are needed many times in the naïve recursion. If we store them, we avoid recomputing.

Putting those together gives the recurrence:

dp[i] = max(dp[i-1], nums[i] + dp[i-2])

with base cases dp[-1] = 0 (nothing before the first house) and dp[0] = nums[0].

The why behind the recurrence is simple: at each house you make a local, irreversible decision—rob it or skip it—but that decision only needs to know the two best outcomes that came before it. No need to look further back; the future can’t affect the past. That’s why we can collapse the whole table into just two variables and sweep once from left to right. It’s like watching a heist crew move down a street, each member deciding whether to take the current loot based only on what the two previous members accomplished.

Wielding the Power (Code & Examples)

The struggle: naïve recursion

def rob_recursive(nums, i):
    if i < 0:
        return 0
    # either rob i and skip i-1, or skip i
    return max(
        rob_recursive(nums, i-2) + nums[i],
        rob_recursive(nums, i-1)
    )

This is elegant but painfully slow—each call spawns two more, leading to that dreaded O(2ⁿ) time. I spent an hour debugging why my solution timed out on a 30‑element test case, feeling like I was trying to pick a lock with a spaghetti strand.

The victory: bottom‑up O(1) space

def rob(nums):
    """
    Returns the maximum amount of money that can be robbed
    without robbing two adjacent houses.
    """
    prev_two, prev_one = 0, 0   # dp[i-2], dp[i-1]
    for money in nums:
        current = max(prev_one, prev_two + money)
        prev_two, prev_one = prev_one, current
    return prev_one

Why this works:

• prev_two holds dp[i-2] (best loot up to the house before the previous one).
• prev_one holds dp[i-1] (best loot up to the previous house).
• For each house we compute the best loot including this house (prev_two + money) or excluding it (prev_one).
• Then we slide the window forward.

Common traps to avoid

Trap	What happens	Fix
Forgetting the empty list	Returns None or throws index error	Guard with if not nums: return 0 (or let the loop handle it because prev_one starts at 0)
Off‑by‑one when seeding	Using nums[0] for prev_two breaks the recurrence	Start both accumulators at 0; the first iteration correctly computes max(0, 0 + nums[0])
Using an array when O(1) is possible	Extra memory, still fine but misses the “elegant” insight	Stick to two variables unless you need the full table for debugging

A second interview flavor: House Robber II (circular street)

Sometimes the houses form a circle, meaning you can’t rob both the first and last house. The trick? Run the linear solver twice:

1. Exclude the first house, solve on nums[1:].
2. Exclude the last house, solve on [:-1]. Take the max of the two results.

def rob_circular(nums):
    if len(nums) == 1:
        return nums[0]
    return max(rob(nums[1:]), rob(nums[:-1]))

Same O(n) time, O(1) extra space—just a tiny wrapper around our core routine.

Why This New Power Matters

Mastering this pattern feels like unlocking a universal key. Suddenly, problems that looked like “pick or skip” puzzles—Maximum Sum of Non‑Adjacent Elements, Delete and Earn, Minimum Cost to Paint Houses—all bow to the same two‑variable DP trick. You stop dreading the recursion tree and start seeing the state you need to carry forward.

More than that, you gain confidence. When an interviewer throws a twist (circular arrangement, extra constraints, profit penalties), you know the first step: identify the decision point and the minimal history required to evaluate it. That’s the heart of dynamic programming, and the House Robber example is the perfect training ground.

So here’s my challenge to you: take the rob function above, tweak it to handle a negative‑value twist (you may now choose to skip a house even if it reduces total loss), and see if you can still keep it O(n) and O(1). Drop your solution in the comments or share a link to your gist—I’d love to see how you’ve made the heist your own.

Happy coding, and may your next interview feel less like a laser‑grid crawl and more like a smooth walk down a sun‑lit street, loot bag swinging happily at your side! 🚀