Introduction

House Robber is a classic dynamic programming problem because each decision affects the next one. At every house, you either rob it and skip the previous house, or skip it and keep the best result so far. Once you phrase the problem that way, the optimal recurrence becomes simple and efficient.

Define the State Clearly

Let dp[i] mean the maximum amount of money you can rob from houses 0 through i inclusive.

At house i, there are only two sensible choices:

• do not rob house i, so the answer stays dp[i - 1]
• rob house i, so you add nums[i] to dp[i - 2]

That gives the recurrence:

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

This is the heart of the problem. Everything else is just handling the first few houses cleanly.

Build the Straightforward Dynamic Programming Solution

A simple implementation uses an array.

1def rob(nums):
2    if not nums:
3        return 0
4    if len(nums) == 1:
5        return nums[0]
6
7    dp = [0] * len(nums)
8    dp[0] = nums[0]
9    dp[1] = max(nums[0], nums[1])
10
11    for i in range(2, len(nums)):
12        dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
13
14    return dp[-1]

This is already optimal in time at O(n), because every house is processed once.

For example, with nums = [2, 7, 9, 3, 1], the DP evolves like this:

• 'dp[0] = 2'
• 'dp[1] = 7'
• 'dp[2] = 11'
• 'dp[3] = 11'
• 'dp[4] = 12'

So the answer is 12.

Reduce Space to O(1)

You do not actually need the whole array because each step depends only on the previous two states.

1def rob(nums):
2    prev2 = 0
3    prev1 = 0
4
5    for value in nums:
6        current = max(prev1, prev2 + value)
7        prev2 = prev1
8        prev1 = current
9
10    return prev1

This version is the one many interviewers hope you reach after first explaining the DP recurrence.

The variables mean:

• 'prev1: best answer up to the previous house'
• 'prev2: best answer up to the house before that'

That makes the code both space-efficient and easy to justify.

Think in Terms of "Take or Skip"

A good interview habit is explaining the problem as a binary choice at each index:

• if I take this house, I must skip the previous one
• if I skip this house, I keep the previous best

That mental model generalizes well to many dynamic programming problems involving adjacency constraints. House Robber is often one of the first places candidates learn to recognize that pattern.

Handle Edge Cases Early

The important edge cases are:

• empty list
• one house
• two houses

Those are not just annoying details. They define the base cases that make the recurrence valid.

print(rob([]))
print(rob([5]))
print(rob([2, 1]))

Once those are correct, the main loop becomes very straightforward.

Recognize the Variants

LeetCode also has related variants such as House Robber II, where houses are arranged in a circle, and House Robber III, where houses form a tree. The linear version in this problem is the foundation for those harder forms.

So even though House Robber itself is simple, it teaches a reusable DP structure:

• define state
• express the choice
• reduce space if only a few prior states matter

Common Pitfalls

• Greedily taking the larger of two adjacent houses instead of solving the global optimization problem.
• Forgetting that the best answer at index i depends on i - 2, not only on local comparisons.
• Skipping edge cases for empty and very short input lists.
• Writing a full DP array and then not noticing the problem only needs two previous states.
• Memorizing the formula without being able to explain the take-versus-skip choice behind it.

Summary

• House Robber is a dynamic programming problem built on a take-or-skip choice at each house.
• The recurrence is max(previous_best, two_back_best + current_value).
• A full DP array works in O(n) time, but only two previous states are needed.
• Handling short inputs cleanly gives you the correct base cases.
• The problem is simple, but the pattern generalizes to many stronger DP interview questions.