House Robber
Problem
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, where adjacent houses cannot be robbed on the same night.
- 1 ≤ nums.length ≤ 100
- 0 ≤ nums[i] ≤ 400
Example
nums = [2,7,9,3,1]12The brute-force approach tries all combinations of robbing or skipping houses, which is exponential. The optimal strategy uses recursion with memoization to avoid redundant calculations. Starting from the last house (index 4), the algorithm decides whether to rob it plus the best from houses before the adjacent one (index 2), or skip it and take the best from the previous house (index 3). For example, robbing house 4 (value 1) plus dp(2) (which is 11) yields 12, while skipping house 4 and taking dp(3) (which is 9) yields 9. The maximum is 12. This decision process repeats recursively, caching results to avoid recomputation.
Approach
Straightforward Solution
A brute-force recursive approach tries all subsets of houses to rob, leading to exponential time complexity due to repeated calculations of the same subproblems.
Core Observation
The maximum amount that can be robbed up to house i depends only on the decisions made for houses before i, specifically whether house i-1 was robbed or not, creating overlapping subproblems with optimal substructure.
Path to Optimal
PreviewRecognizing the overlapping subproblems and optimal substructure leads to a dynamic programming solution…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewImplement a top-down recursive function with memoization that returns dp(i), the maximum amount that can be robbed up to house i. The function returns 0 for negative indices (base case)…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n)
Each house index from 0 to n-1 is computed once and stored in the memo dictionary, avoiding repeated calculations.
Space
O(n)
The memo dictionary stores results for each house index, and the recursion stack can go up to O(n) in the worst case.
Pattern Spotlight
Dynamic Programming (Top-Down Memoization)
When a problem involves making a sequence of decisions with overlapping subproblems and optimal substructure, define a recursive state representing the problem up to a certain index, then cache results to avoid redundant work and achieve linear time.
Solution
| 1 | class Solution:
|
| 2 | def rob(self, nums: list[int]) -> int:
|
| 3 | memo = {}
|
| 4 |
|
| 5 | def dp(i):
|
| 6 | if i < 0:
|
| 7 | return 0
|
| 8 | if i in memo:
|
| 9 | return memo[i]
|
| 10 |
|
| 11 | result = max(nums[i] + dp(i - 2), dp(i - 1))
|
| 12 | memo[i] = result
|
| 13 | return result
|
| 14 |
|
| 15 | return dp(len(nums) - 1) |
Step-by-Step Solution
Initialize Memoization Cache for Subproblem Results
| 3 | memo = {}
|
Objective
To create a dictionary that stores the maximum robbery amount for each house index to avoid redundant recursive computations.
Key Insight
Memoization transforms the naive exponential recursion into a linear time algorithm by caching results of subproblems. This cache acts as a memory of previously solved states, ensuring each state is computed once and reused whenever needed.
Interview Quick-Check
Core Logic
Memoization stores dp(i) results, preventing repeated calculations of the same subproblems.
Common Pitfalls & Bugs
Forgetting to memoize results leads to exponential time due to repeated recursive calls.
Define Recursive Function to Compute Maximum Robbery Up to Index i
To recursively compute the maximum amount that can be robbed from houses 0 to i, using memoization to cache results.
Return Maximum Robbery Amount for All Houses
To initiate the recursive computation from the last house and return the final maximum robbery amount.
2 more steps with full analysis available on Pro.
Line Analysis
This solution has 3 Critical lines interviewers watch for.
return memo[i]Compute the maximum robbery amount by choosing to rob house i plus dp(i-2) or skip house i and take dp(i-1).
This recurrence captures the core decision: robbing house i excludes adjacent house i-1, so the next valid house is i-2; skipping house i allows considering house i-1. Taking the max ensures optimality.
if i < 0:Return 0 if the index i is negative, representing no houses left to rob.
This base case prevents invalid indices and terminates recursion, ensuring correctness and preventing infinite recursion.
return 0Check if the result for index i is already computed and cached.
This memoization check avoids recomputing dp(i), which is critical for achieving linear time complexity.
Full line-by-line criticality + rationale for all 9 lines available on Pro.
Test Your Understanding
Why does the recursive function consider dp(i - 2) when deciding to rob house i?
See the answer with Pro.
Related Problems
Dynamic Programming pattern
Don't just read it. Drill it.
Reconstruct House Robber from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the House Robber drill