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
Recognizing the overlapping subproblems and optimal substructure leads to a dynamic programming solution. By defining dp(i) as the maximum amount that can be robbed from houses 0 to i, the problem breaks down into choosing between robbing house i plus dp(i-2), or skipping house i and taking dp(i-1). Memoization caches these results, reducing time complexity from exponential to linear.
Optimal Approach
Implement 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). For each i, it computes the maximum of robbing house i plus dp(i-2) or skipping house i and taking dp(i-1). Memoization ensures each state is computed once, resulting in O(n) time and space complexity.
Time
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) |
| 1 | import java.util.HashMap; |
| 2 | import java.util.Map; |
| 3 | |
| 4 | public class Solution { |
| 5 | public int rob(int[] nums) { |
| 6 | Map<Integer, Integer> memo = new HashMap<>(); |
| 7 | |
| 8 | return dp(nums, nums.length - 1, memo); |
| 9 | } |
| 10 | |
| 11 | private int dp(int[] nums, int i, Map<Integer, Integer> memo) { |
| 12 | if (i < 0) { |
| 13 | return 0; |
| 14 | } |
| 15 | if (memo.containsKey(i)) { |
| 16 | return memo.get(i); |
| 17 | } |
| 18 | |
| 19 | int result = Math.max(nums[i] + dp(nums, i - 2, memo), dp(nums, i - 1, memo)); |
| 20 | memo.put(i, result); |
| 21 | return result; |
| 22 | } |
| 23 | } |
| 1 | #include <vector> |
| 2 | #include <unordered_map> |
| 3 | #include <algorithm> |
| 4 | |
| 5 | using namespace std; |
| 6 | |
| 7 | class Solution { |
| 8 | public: |
| 9 | int rob(vector<int>& nums) { |
| 10 | unordered_map<int, int> memo; |
| 11 | return dp(nums, (int)nums.size() - 1, memo); |
| 12 | } |
| 13 | |
| 14 | private: |
| 15 | int dp(const vector<int>& nums, int i, unordered_map<int, int>& memo) { |
| 16 | if (i < 0) { |
| 17 | return 0; |
| 18 | } |
| 19 | auto it = memo.find(i); |
| 20 | if (it != memo.end()) { |
| 21 | return it->second; |
| 22 | } |
| 23 | |
| 24 | int result = max(nums[i] + dp(nums, i - 2, memo), dp(nums, i - 1, memo)); |
| 25 | memo[i] = result; |
| 26 | return result; |
| 27 | } |
| 28 | }; |
| 1 | var rob = function(nums) { |
| 2 | const memo = new Map(); |
| 3 | |
| 4 | function dp(i) { |
| 5 | if (i < 0) { |
| 6 | return 0; |
| 7 | } |
| 8 | if (memo.has(i)) { |
| 9 | return memo.get(i); |
| 10 | } |
| 11 | |
| 12 | const result = Math.max(nums[i] + dp(i - 2), dp(i - 1)); |
| 13 | memo.set(i, result); |
| 14 | return result; |
| 15 | } |
| 16 | |
| 17 | return dp(nums.length - 1); |
| 18 | }; |
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
| 5 | def dp(i):
|
| 6 | if i < 0:
|
| 7 | return 0
|
| 8 | if i in memo:
|
| 9 | return memo[i]
|
| 11 | result = max(nums[i] + dp(i - 2), dp(i - 1))
|
| 12 | memo[i] = result
|
| 13 | return result
|
Objective
To recursively compute the maximum amount that can be robbed from houses 0 to i, using memoization to cache results.
Key Insight
The recursive function dp(i) embodies the problem's optimal substructure by deciding whether to rob house i plus dp(i-2) or skip house i and take dp(i-1). The base case returns 0 for invalid indices, ensuring recursion termination. Memoization ensures each state is computed once, converting exponential recursion into linear time.
Interview Quick-Check
Core Logic
The recurrence dp(i) = max(nums[i] + dp(i-2), dp(i-1)) captures the choice between robbing or skipping house i.
State & Boundaries
Base case dp(i) = 0 for i < 0 prevents invalid indices and terminates recursion.
Common Pitfalls & Bugs
Not checking the memo before recursion causes redundant computations and timeouts.
Return Maximum Robbery Amount for All Houses
| 15 | return dp(len(nums) - 1) |
Objective
To initiate the recursive computation from the last house and return the final maximum robbery amount.
Key Insight
Starting the recursion from the last house index ensures the entire problem is solved. The recursive calls break down the problem into smaller subproblems, and memoization guarantees efficiency. The returned value represents the maximum amount that can be robbed without alerting the police.
Interview Quick-Check
Core Logic
Calling dp(len(nums) - 1) computes the maximum robbery amount considering all houses.
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.
memo = {}Initialize a memoization dictionary to cache results of subproblems.
This dictionary is essential to store computed dp(i) values, preventing redundant recursive calls and reducing time complexity from exponential to linear.
if i in memo:Return the cached result for index i if available.
Returning the cached value immediately prunes the recursion tree, preventing exponential blowup.
result = max(nums[i] + dp(i - 2), dp(i - 1))Store the computed result in the memo dictionary for index i.
Caching the result ensures that future calls to dp(i) return instantly, enabling efficient memoized recursion.
return dp(len(nums) - 1)Start the recursion from the last house and return the maximum robbery amount.
This call triggers the entire memoized recursion, solving the problem for all houses and returning the final answer.
def dp(i):Define the recursive function dp that computes the maximum robbery amount up to house i.
Encapsulating the problem in a recursive function with parameter i allows breaking down the problem into smaller subproblems with overlapping states.
memo[i] = resultReturn the computed maximum robbery amount for index i.
Returning the result completes the recursive call, propagating the optimal solution up the call stack.
Test Your Understanding
Why does the recursive function consider dp(i - 2) when deciding to rob house i?
Because robbing house i prohibits robbing the adjacent house i-1, so the next valid house to consider is i-2, ensuring no two adjacent houses are robbed.
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