House Robber
Can't rob two adjacent houses. At each house i: either rob it (value[i] + best from i−2) or skip it (best from i−1). dp[i] = max(dp[i−1], dp[i−2] + nums[i]). The 'skip or take' pattern appears everywhere in DP.
How It Works
House Robber-style 1D DP models a take-or-skip decision at every index under a no-two-adjacent constraint. Define dp[i] as the best total using the first i houses: either skip house i (dp[i-1]) or take it and add its value to dp[i-2]. The recurrence dp[i] = max(dp[i-1], dp[i-2] + nums[i]) captures the entire decision space without enumerating the exponential number of valid subsets.
Because each state depends only on the two previous states, the O(n) table compresses to two rolling variables, giving O(n) time and O(1) space. This take-or-skip template generalizes to many linear DP problems.
Step-by-Step Visualization
Code
static int rob(int[] nums) {
int prev2 = 0, prev1 = 0;
for (int num : nums) {
int curr = Math.max(prev1, prev2 + num);
prev2 = prev1;
prev1 = curr;
}
return prev1;
}
// rob(new int[]{2,7,9,3,1}) → 12 (rob houses 0,2,4: 2+9+1=12)Tips & Gotchas
Practice Problems
- 1House Robber
- 2House Robber II
- 3Delete and Earn
- 4Maximum Sum of Non-Adjacent Elements
About the 1D DP Pattern
The state is a single variable (usually an index). Each dp[i] depends on a few previous values like dp[i−1] or dp[i−2]. Often you can optimize space by keeping only the last 2-3 values instead of the whole array.
The framework: 1) Define state (what changes between subproblems). 2) Write recurrence relation. 3) Identify base cases. 4) Decide iteration order. Most DP is either 1D, 2D, or interval-based.
Common Dynamic Programming Interview Problems
- Climbing Stairs
- Coin Change
- Longest Common Subsequence
- 0/1 Knapsack
- Edit Distance
- House Robber
- Longest Increasing Subsequence
- Word Break
Frequently Asked Questions
How do I recognize that a problem is 1D take-or-skip DP?
Look for a linear sequence where each element is either used or not, a constraint tying adjacent choices together, and an objective to maximize or minimize a total. If choosing element i only restricts elements i-1 or i+1, the two-term recurrence usually applies.
When can I drop the DP array for O(1) space?
Whenever the recurrence references a fixed number of recent states — here dp[i-1] and dp[i-2] — you can keep just those in variables and update them as you scan. Problems needing arbitrary lookback or path reconstruction still require the full table.
How does House Robber II handle the circular street?
When the first and last houses are adjacent, you cannot rob both, so you run the linear solution twice: once excluding the first house and once excluding the last. The answer is the maximum of the two runs, which is still O(n) time.