1D DP Patterns
The four one-dimensional DP shapes you meet most - take or skip, minimum coins, counting ways, and jumps - each with state, transition, base case and answer.
The problem
Most early DP problems have a state that is a single index or a single number: "the best answer using the first i items" or "the best answer for total s". That is a 1D DP, a table with one dimension.
This lesson covers four shapes. Each is the same loop with a different transition.
| Shape | State dp[i] | Transition idea |
|---|---|---|
| Take or skip | best value using the first i items | skip item i, or take it and skip its neighbour |
| Min coins | fewest coins to make amount i | try every coin as the last one |
| Count ways | number of ways to make i | add the ways of every smaller state |
| Jumps | fewest jumps to reach position i | try every position that can jump to i |
1 of 7