Core pattern
Linear DP
Step 3 of 14Pattern 1 of 7
×How to recognize it fast
This is the pattern for problems where the best answer at position i depends on the previous one or two positions.
When you see
stairsadjacent restrictionbest till indexprefix ending heremax sum subarraycannot choose consecutive items
Think
- The current answer depends on previous 1-2 positions.
- I am choosing between taking the current value or skipping it.
What to do once the pattern is clear
Core trick
- Define dp[i] as the best answer up to index i.
- Write the recurrence before thinking about space optimization.
- If the transition only touches i - 1 and i - 2, compress to two rolling variables.
Shortcut recognition
No adjacent choicesMaximize till current pointBest prefix ending here
Hidden trick
Many linear DP questions become much simpler once you stop storing the full array and keep only the last two states.
House Robber recurrence
dp[i] = max(dp[i - 1], nums[i] + dp[i - 2])