Lesson 28.3 · DP Foundations: 1D
Take-or-Skip Decisions
Many 1D problems ask, at each item, whether to use it. dp[i] = best of (skip item i) and (take item i plus the best compatible earlier state).
12 min
Think of it like this
A burglar walking down a street who can't rob two neighbouring houses without setting off the alarms. At each house: rob it and add the best total from two houses back, or skip it and keep the best total so far.
1.House Robber shape
dp[i] = the most money from houses 0..i. Skip house i: dp[i − 1]. Take it: nums[i] + dp[i − 2]. So dp[i] = max(dp[i − 1], dp[i − 2] + nums[i]).
The same shape appears whenever choosing an item forbids its neighbours: Delete and Earn (choosing value v deletes v − 1 and v + 1) becomes House Robber over value buckets. A circular street (House Robber II) runs it twice: once without the first house, once without the last.
nums = [2, 7, 9, 3, 1]dp(list)
Step 1/5dp[0] = 2.
Remember
- Skip: dp[i − 1]. Take: value + dp of the last compatible state.
- Circular: solve two linear cases.
- Transform other problems into this shape.
Common mistakes
- Greedy picking the largest values (fails on [2, 1, 1, 2]).