House Robber Problem
Watch how 1D dynamic programming finds the maximum money that can be robbed without hitting adjacent houses.
Time: O(n)
Space: O(1)
1D DP Array
Decision Making
Fast (300ms)Slow (2000ms)
Progress: Step 1 of 0Phase: start
Neighborhood (Planning...)
2
House 0
7
House 1
9
House 2
3
House 3
1
House 4
DP Array (Maximum Money Up To Each House)
dp[0]
$0
dp[1]
$0
dp[2]
$0
dp[3]
$0
dp[4]
$0
-
-
-
-
-
Current Step:
Click Start to begin the House Robber visualization
Algorithm Details
Time Complexity:
O(n)Space Complexity:
O(1)With Reconstruction:
O(n)Type:1D DP Array
Real-world Applications
- •Job scheduling with conflicts
- •Maximum profit from non-adjacent investments
- •Resource allocation with constraints
- •Activity selection problems
- •Maximum sum with no adjacent elements
- •Stock trading with cooldown periods
Key DP Concepts
- ✓Constraint: Cannot rob adjacent houses
- ✓State: dp[i] = max money up to house i
- ℹRecurrence: dp[i] = max(rob, skip)
- ℹBase Cases: dp[0] = nums[0], dp[1] = max(nums[0], nums[1])
Problem Variants
- •House Robber II (circular array)
- •House Robber III (binary tree)
- •Maximum sum with k distance apart
- •Delete and earn (similar pattern)