Dynamic programming becomes much easier when you stop beginning with an array. Begin by defining a question whose answer can be reused.
Define the state in a sentence
A state should specify exactly what its inputs mean. For example: dp[i] is the best score obtainable from the first i items, or solve(i, remaining) is the number of valid completions from position i with a given balance. If the sentence is ambiguous, the implementation will be too.
Derive the transition
List the choices available from one state and identify the smaller states they lead to. Then decide how those results combine: minimum, maximum, sum, or boolean OR. The transition should follow from the problem, not from a memorized template.
Finish the model
Name the base cases, the evaluation order, and the answer state. Memoization evaluates only requested states; tabulation makes ordering explicit and may reduce overhead. Before optimizing memory, write a correct recurrence and test tiny cases by hand.
Continue with the book
Explore the full treatment, worked examples, and exercises in Algorithmic Edge.
Adapted from Algorithmic Edge, published by Choral Software. Article text and original examples © 2026 Choral Software. All rights reserved.