← Back to DevBytes
Python August 05, 2026 7 min read

Solving House Robber Problem in Python: Step-by-Step Guide

Introduction to the House Robber Problem

The House Robber problem is one of the most iconic dynamic programming challenges you will encounter in coding interviews and competitive programming. It elegantly demonstrates how a seemingly complex decision-making problem can be broken down into smaller overlapping subproblems. In this tutorial, we will walk through the problem from a naive recursive solution all the way to an optimized constant-space dynamic programming approach in Python.

What Is the House Robber Problem?

Imagine a street lined with houses, each containing a certain amount of money. You are a robber planning to rob houses along this street. However, adjacent houses have connected security systems, and if two adjacent houses are robbed on the same night, the alarm will trigger and alert the police. Given a list of non-negative integers representing the amount of money in each house, your goal is to determine the maximum amount of money you can rob tonight without alerting the authorities.

Formally, given an array nums of length n, find the maximum sum of a subsequence where no two selected elements are adjacent.

Why It Matters

The House Robber problem matters because it teaches the foundational principles of dynamic programming in a digestible way. Mastering it helps you understand:

These concepts transfer directly to harder problems such as the Coin Change problem, the Knapsack problem, and various pathfinding challenges on grids.

Understanding the Recurrence Relation

The key insight is that for every house, you have exactly two choices: rob it or skip it. If you rob the current house, you cannot rob the previous one, so your total becomes the current house's value plus the maximum loot from two houses before. If you skip the current house, your total remains the maximum loot up to the previous house.

This leads to the recurrence:

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

Where dp[i] represents the maximum amount that can be robbed from the first i+1 houses. The base cases are dp[0] = nums[0] and dp[1] = max(nums[0], nums[1]).

Step 1: Brute Force Recursive Solution

The most intuitive approach is to recursively explore every possible combination of robbing or skipping each house. While correct, this solution has an exponential time complexity of O(2^n) because it recomputes the same subproblems repeatedly.

def rob_recursive(nums):
    def helper(i):
        if i < 0:
            return 0
        # Either rob this house and skip the previous, or skip this house
        rob_current = nums[i] + helper(i - 2)
        skip_current = helper(i - 1)
        return max(rob_current, skip_current)
    
    return helper(len(nums) - 1)

# Example usage
houses = [2, 7, 9, 3, 1]
print(rob_recursive(houses))  # Output: 12

For the input [2, 7, 9, 3, 1], the optimal selection is robbing houses at indices 0, 2, and 4, yielding 2 + 9 + 1 = 12.

Step 2: Top-Down Memoization

To eliminate redundant computations, we can cache the results of subproblems using a dictionary or a list. This technique, known as memoization, reduces the time complexity to O(n) while keeping the recursive structure intact.

def rob_memo(nums):
    memo = {}
    
    def helper(i):
        if i < 0:
            return 0
        if i in memo:
            return memo[i]
        
        rob_current = nums[i] + helper(i - 2)
        skip_current = helper(i - 1)
        memo[i] = max(rob_current, skip_current)
        return memo[i]
    
    return helper(len(nums) - 1)

houses = [2, 7, 9, 3, 1]
print(rob_memo(houses))  # Output: 12

This version is significantly faster for larger inputs, but it still consumes O(n) stack space due to recursion, which can cause a RecursionError on very large inputs.

Step 3: Bottom-Up Tabulation

To avoid recursion entirely, we can build the solution iteratively from the ground up. We create a dp array where each entry is computed using previously stored values. This approach has O(n) time and O(n) space complexity.

def rob_tabulation(nums):
    n = len(nums)
    if n == 0:
        return 0
    if n == 1:
        return nums[0]
    
    dp = [0] * n
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])
    
    for i in range(2, n):
        dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
    
    return dp[-1]

houses = [2, 7, 9, 3, 1]
print(rob_tabulation(houses))  # Output: 12

Notice how we handle edge cases explicitly: an empty list returns 0, and a single-element list returns that element. These guards prevent index errors and make the function robust.

Step 4: Space-Optimized Solution

Looking closely at the recurrence, we only ever need the previous two values to compute the current one. This means we can replace the entire dp array with two variables, reducing the space complexity to O(1) while maintaining O(n) time complexity.

def rob_optimized(nums):
    prev2 = 0  # dp[i-2]
    prev1 = 0  # dp[i-1]
    
    for num in nums:
        current = max(prev1, prev2 + num)
        prev2 = prev1
        prev1 = current
    
    return prev1

houses = [2, 7, 9, 3, 1]
print(rob_optimized(houses))  # Output: 12

This is the most efficient version of the solution. It is concise, easy to reason about, and performs well even on large inputs. The variables prev1 and prev2 slide forward through the array, always holding the optimal loot up to the previous house and the house before that.

Handling Edge Cases

A robust solution must account for edge cases that often appear in interviews and automated testing platforms. Consider the following scenarios:

The space-optimized solution handles all of these naturally because prev1 and prev2 start at zero, and the loop gracefully processes any length of input.

Testing Your Solution

Writing tests ensures your implementation behaves correctly across a variety of inputs. Here is a simple test suite using Python's built-in assert statements:

def test_rob():
    assert rob_optimized([]) == 0
    assert rob_optimized([5]) == 5
    assert rob_optimized([3, 5]) == 5
    assert rob_optimized([2, 7, 9, 3, 1]) == 12
    assert rob_optimized([1, 2, 3, 1]) == 4
    assert rob_optimized([4, 4, 4, 4]) == 8
    assert rob_optimized([1, 2, 3, 4, 5]) == 9
    assert rob_optimized([10, 1, 1, 10]) == 20
    print("All tests passed!")

test_rob()

Running this suite confirms that the function handles typical cases, edge cases, and patterns where alternating selections yield the best result.

Best Practices

When solving dynamic programming problems like House Robber, keep the following best practices in mind:

Variations to Explore

Once you are comfortable with the basic House Robber problem, try these variations to deepen your understanding:

Conclusion

The House Robber problem is a perfect gateway into the world of dynamic programming. By progressing from a naive recursive solution to a space-optimized iterative one, you learn how to identify overlapping subproblems, formulate recurrence relations, and incrementally improve both time and space complexity. The patterns you internalize here, sliding state variables, bottom-up tabulation, and careful edge-case handling, will serve you across countless algorithmic challenges. Practice the variations, write thorough tests, and you will be well-equipped to tackle even the most demanding dynamic programming questions in your next coding interview.

— Ad —

Google AdSense will appear here after approval

← Back to all articles