core practice · coding problem
House robber (1D DP)
Given values along a line, pick a non-adjacent subset with maximum sum.
The mechanism
Dynamic programming is recursion with the repeated work cached. Define the state (what does dp[i] mean?), the recurrence (how does dp[i] build on earlier states?), and the base case. 1D DP means the state is a single index along a sequence.
Expected evidence
rob([2,7,9,3,1]) -> 12
Try this drill in the practice workspace →
Hints when you need them
- Define dp[i] = best sum using houses 0..i.
- dp[i] = max(dp[i-1], dp[i-2] + value[i]).
Watch for these mistakes
- Starting to code before clearly defining what dp[i] represents
- Wrong iteration order so a state is read before it is computed
- Missing or wrong base cases