Chapter 2: To Rob or Not to Rob - House Robber

In our last chapter, we established a powerful framework for solving dynamic programming problems: starting with a simple recursive idea, optimizing it with memoization, and finally, perfecting it with an iterative, bottom-up approach. Now, let's apply that same framework to a new challenge: LeetCode's "House Robber" (Problem #198).

This problem is a fantastic next step because it forces us to make a decision at each stage, adding a layer of complexity that builds perfectly on what we've already learned.

The Problem:

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. The only constraint stopping you from robbing each of them is that adjacent houses have security systems connected, and it will automatically contact the police if two adjacent houses are broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

For example:

• If nums = [1, 2, 3, 1], the maximum you can rob is 4 (rob house 1 with money 1, and house 3 with money 3).

• If nums = [2, 7, 9, 3, 1], the maximum is 12 (rob house 1 with money 2, house 3 with money 9, and house 5 with money 1).

Approach 1: The Recursive Solution

Let's think about this recursively. Imagine we are standing in front of the last house, house n. We have two choices:

1. Rob house n: If we rob this house, we get its money (nums[n]). However, we cannot rob the previous house (n-1). This means our total loot would be nums[n] plus the maximum we could have robbed from houses up to n-2.

2. Don't rob house n: If we skip this house, we get no money from it. Our total loot would simply be the maximum we could have robbed from houses up to n-1.

The optimal solution is the one that gives us more money. This gives us our recursive formula: max_rob(n) = max( nums[n] + max_rob(n-2), max_rob(n-1) )

We need base cases to terminate the recursion. Let's define our function rob_from(i) as the maximum money we can rob from house i to the beginning of the street.

• rob_from(0): We only have one house, so we rob it. The result is nums[0].

• rob_from(1): We have two houses. We rob the one with more money. The result is max(nums[0], nums[1]).

Let's write the code.

from typing import List

def rob_recursive(nums: List[int]) -> int:
    def solve(i):
        # Base case: if we are out of bounds, we can't rob anything.
        if i < 0:
            return 0

        # The core recursive choice
        # Option 1: Rob house i + whatever we got from i-2
        option1 = nums[i] + solve(i - 2)
        # Option 2: Don't rob house i, take whatever we got from i-1
        option2 = solve(i - 1)

        return max(option1, option2)

    # Start the process from the last house
    return solve(len(nums) - 1)

# Trying it out
# print(rob_recursive([2, 7, 9, 3, 1])) # Output: 12
# print(rob_recursive([ ... a long list ... ])) # This will be very slow!

Just like with Climbing Stairs, this solution is correct but terribly inefficient. We are recalculating solve(i) for the same i multiple times, leading to an exponential time complexity.

Approach 2: Memoization with a Decorator (Top-Down DP)

We know the drill. The problem is redundant computation, and the solution is caching. Let's bring back our trusty friend @functools.lru_cache to instantly optimize our recursive solution.

import functools
from typing import List

class Solution:
    def rob_memoized(self, nums: List[int]) -> int:

        @functools.lru_cache(maxsize=None)
        def solve(i):
            if i < 0:
                return 0

            option1 = nums[i] + solve(i - 2)
            option2 = solve(i - 1)

            return max(option1, option2)

        return solve(len(nums) - 1)

# Trying it out
# solver = Solution()
# print(solver.rob_memoized([2, 7, 9, 3, 1])) # Instantaneous!

Once again, a single line turns our sluggish algorithm into a high-performance one. We've preserved the intuitive recursive logic while eliminating the repeated work. This is top-down DP at its finest.

Approach 3: Iteration (Bottom-Up DP)

Now, let's think about this from the ground up. Instead of starting at the end and working backward, we'll start at the beginning and build our solution forward. This is tabulation.

We can ask: what is the max loot we can have after visiting house i? It's either the max loot from the previous house (i-1, if we skip house i), or the loot from house i plus the max loot from two houses ago (i-2).

This is the exact same logic, but we'll compute it iteratively. Let's use two variables to keep track of the maximum loot we could have from the previous two steps.

Let rob1 be the max loot ending at house i-1. Let rob2 be the max loot ending at house i-2.

When we get to house i, the new max loot will be max(nums[i] + rob2, rob1).

def rob_iterative(nums: List[int]) -> int:
    # We use two variables to track the max loot at i-1 and i-2
    rob1, rob2 = 0, 0

    # [rob2, rob1, n, n+1, ...]
    # For each house n, we decide whether to rob it
    for n in nums:
        # The new max is either the previous max (rob1),
        # or this house's money + the max from two houses ago (rob2)
        temp = max(n + rob2, rob1)
        # Update our pointers for the next house
        rob2 = rob1
        rob1 = temp

    return rob1

# Trying it out
# print(rob_iterative([2, 7, 9, 3, 1])) # Output: 12

This solution is the most optimal. It has a linear time complexity since we iterate through the list once, and it has a constant space complexity because we only use two variables regardless of the input size.

Conclusion

In this chapter, we escalated the difficulty slightly by introducing a decision-making component. Yet, our core strategy held up perfectly. We started with an intuitive but slow recursive function, made it instantly fast with memoization, and finally refined it into the most efficient iterative solution.

You are now internalizing the fundamental pattern of dynamic programming. As we move to more complex problems, this three-step thinking process will be your most valuable tool.