1D DP
Intermediate · 22 min read · Problem-Solving Patterns, Dynamic Programming
Climbing stairs, house robber, maximum subarray and longest increasing subsequence.
The simplest DP family walks along a sequence once. At each position you make a small decision — take this element or not, extend the current run or restart, which earlier element to attach to — and the best answer up to here depends only on answers at earlier positions.
Shape 1: take or skip — house robber
State: best[i] = most money from houses 0..i. Choice at house i: skip it (best[i − 1]) or take it (a[i] + best[i − 2]).
Shape 2: best ending here — Kadane's algorithm
Define the state as the best subarray ending exactly at i. That subarray either extends the best one ending at i − 1, or starts fresh at i — whichever is larger:
Shape 3: look back at all earlier positions — LIS
State: dp[i] = length of the longest increasing subsequence ending at i. It extends the best one ending at any earlier j with a[j] < a[i]:
Shape 4: segmenting a string
dp[i] = ways to decode the first i characters. The last piece is either one digit (1–9) or two digits (10–26):
Patterns at a glance
Practice ladder
Interview questions
- Why does Kadane's algorithm work?
- How does the O(n log n) LIS algorithm work?
Further reading
Key takeaways
- 1D DP walks the sequence once; the state is usually "best up to i" or "best ending at i".
- Take or skip (house robber); extend or restart (Kadane); look back at all j (LIS, word break).
- Track extra values when signs flip (max and min for products).
- LIS: O(n²) DP, or O(n log n) with sorted tails and binary search.
- Break circular problems into two linear ones.