Dynamic programming is a way to solve problems that reuse the same smaller questions. Instead of calculating an answer repeatedly, solve each subproblem once and remember the result.
Start with a recurrence
Consider the Fibonacci sequence: each value is the sum of the two before it. A straightforward recursive definition repeats work because the same smaller values are calculated many times. A table avoids that repeated calculation by recording each answer as it is found.
Two common styles
Memoization keeps the recursive shape and caches answers on demand. Tabulation builds a table from the smallest cases upward until the target is reached. Both turn repeated work into reuse; the best choice often depends on which subproblems are needed and which style is easier to explain.
A practical checklist
- Define exactly what a subproblem's state means.
- Write how a state's answer depends on smaller states.
- Identify base cases and a valid computation order.
- Count the number of states and work per state.
If there are n states and each takes constant work, the time is often O(n). Dynamic programming is not magic; it is careful bookkeeping for overlapping subproblems with a clear recurrence.