March 24
House Robber
How to model the choice between robbing or skipping each house while respecting the adjacency constraint.
Dynamic Programming Intermediate 18 min TypeScript
You are a robber planning to rob houses along a street.
Each house has some amount of money, given by nums[i].
Adjacent houses cannot be robbed on the same night.
Return the maximum amount of money you can rob.
Example:
Input: nums = [2,7,9,3,1]
Output: 12
Because the best choice is 2 + 9 + 1 = 12.
What to notice before coding
- The problem is about maximizing, not counting.
- The important restriction is adjacency.
- At each position, you choose between carrying the previous best answer or including the current house.
Common mistakes
- making a local greedy choice based on the biggest current house
- forgetting that taking the current house pushes you two houses back
Step 1 - See why local greedy reasoning fails
If you only look at the current house, you may think:
- take the biggest one in front of you
But that breaks quickly.
The problem is not choosing one good house now.
It is choosing a good sequence with no neighbors.
Step 2 - Write the recursive baseline
For the house at index i, you have two options:
- skip
iand move toi + 1 - rob
iand move toi + 2
That creates a natural recursion.
It works, but it recomputes many indexes.
Step 3 - Build the right recurrence
Looking from left to right, the best answer up to house i is:
- either the best answer up to
i - 1 - or the best answer up to
i - 2plusnums[i]
So:
best(i) = max(best(i - 1), best(i - 2) + nums[i])
Step 4 - Keep only the previous two states
You do not need a full table.
You only need to remember:
- the best answer up to the previous house
- the best answer up to two houses before
The interactive editor needs JavaScript. You can still read the prompt and copy the starter code below.
Starter code
export function rob(nums: number[]): number {
// your solution here
return 0
}
Haven't solved it yet?
Viewing the solution now may reduce learning. It's worth trying a bit more.
Open the reference solution
Without JavaScript, the reference solution is shown inline instead of in a dialog.
Solution
Final complexity
Time: O(n)
Space: O(1)
Solution 1 - Recursion with take-or-skip before memoization
Good baseline because it makes the central decision very explicit.
export function rob(nums: number[]): number {
function solve(index: number): number {
if (index >= nums.length) {
return 0
}
return Math.max(solve(index + 1), nums[index] + solve(index + 2))
}
return solve(0)
}It works, but it wastes work by repeating the same indexes.
Solution 2 - Dynamic programming with reduced state in O(1) space
Now the same idea runs in linear time.
export function rob(nums: number[]): number {
let twoHousesBefore = 0
let oneHouseBefore = 0
for (const value of nums) {
const current = Math.max(oneHouseBefore, twoHousesBefore + value)
twoHousesBefore = oneHouseBefore
oneHouseBefore = current
}
return oneHouseBefore
}The strong reasoning here is seeing include-or-skip as the state.
What to say in the interview
A strong short explanation would be:
For each house, I choose between skipping it and keeping the previous best answer, or robbing it and adding the best answer from two houses back. That gives the recurrence
max(best(i - 1), best(i - 2) + nums[i]). Since I only depend on the previous two states, I can reduce space toO(1).
That shows that you:
- found the right decision
- avoided falling into local greedy reasoning
- connected the recurrence to a space optimization
When this pattern shows up again
The same pattern comes back when you need to:
- choose between including or excluding an item
- handle adjacency constraints
- build a linear dynamic programming state with two values
- turn a decision recursion into iteration
The point is not memorizing
rob.
The point is learning how to model a choice with short-range dependency.