Decision DP Pattern
At each state, you make a binary decision: take or skip. The key constraint: can't take two adjacent items. This "include/exclude" pattern appears in many DP problems.
Recurrence
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
dp[i] = max(
dp[i-1], // skip house i
dp[i-2] + nums[i] // rob house i
)
dp[1] = max(nums[0], nums[1])
dp[i] = max(
dp[i-1], // skip house i
dp[i-2] + nums[i] // rob house i
)
Interactive Visualization
Deciding Robbed Skipped
Step 0 of 0
House
—
Rob vs Skip
—
dp[i]
—
Max Loot
—
Ready. Press Play or Next to start.
✓ Done
Speed
C++ — House Robber
int rob(vector<int>& nums) { int n = nums.size(); if (n == 1) return nums[0]; int prev2 = nums[0]; int prev1 = max(nums[0], nums[1]); for (int i = 2; i < n; i++) { int curr = max(prev1, prev2 + nums[i]); prev2 = prev1; prev1 = curr; } return prev1; }
Complexity
Time
O(N)
Single pass.
Space
O(1)
Two variables only.