Dynamic programming is an algorithm design technique that solves a problem by breaking it into overlapping subproblems, solving each subproblem once and storing its result for reuse. Among algorithms it turns many problems with exponential naive solutions, such as counting paths or comparing sequences, into polynomial-time procedures.
The method applies when a problem has two properties: optimal substructure, meaning an optimal solution is built from optimal solutions of smaller parts, and overlapping subproblems, meaning the same smaller parts recur many times. The name, introduced by Richard Bellman in the 1950s, refers to planning a sequence of decisions rather than to writing code.
How dynamic programming works
Every dynamic programming solution rests on a recurrence relation that expresses the answer for a state in terms of answers for smaller states. Designing it involves four decisions: what a state represents, the transition between states, the base cases that need no further breakdown, and the evaluation order that guarantees each state is computed after the states it depends on.
A classic illustration is the Fibonacci sequence. The naive recursive definition recomputes the same values again and again and takes exponential time, roughly O(1.6 to the power n). Storing each value the first time it is computed reduces the work to O(n) time, because every one of the n states is solved exactly once.
The total cost of a dynamic programming algorithm follows a simple rule: number of states multiplied by the work per transition. The table below applies that rule to well-known problems.
| Problem | State | Time | Space |
|---|---|---|---|
| Fibonacci numbers | Index i | O(n) | O(1) with rolling values |
| 0/1 knapsack | Item i and remaining capacity w | O(nW) | O(W) with one row |
| Longest common subsequence | Prefix lengths i and j | O(nm) | O(min(n, m)) for length only |
| Edit distance | Prefix lengths i and j | O(nm) | O(min(n, m)) for distance only |
| Matrix chain multiplication | Interval i to j | O(n cubed) | O(n squared) |
| Shortest paths, Bellman-Ford | Vertex and edge count | O(VE) | O(V) |
Top-down memoization and bottom-up tabulation
There are two standard ways to evaluate a recurrence. Memoization keeps the natural recursive structure and caches each result in a map or array the first time it is computed. Tabulation fills a table iteratively, starting from base cases and moving toward the final answer in an order that respects the dependencies.
| Aspect | Top-down memoization | Bottom-up tabulation |
|---|---|---|
| Code structure | Recursive function plus cache | Loops over a table |
| States computed | Only states actually reached | All states in the table |
| Stack usage | Deep recursion can overflow | No recursion stack |
| Space optimization | Hard to apply | Rolling arrays keep only needed rows |
| Ease of design | Closer to the recurrence | Requires a correct evaluation order |
In practice, memoization is often faster to write and wins when only a sparse subset of states is reachable. Tabulation is preferred for performance-critical code, because it avoids function call overhead and allows space reduction, for example keeping only two rows of an n by m table.
Dynamic programming versus related strategies
Dynamic programming sits between divide and conquer and greedy algorithms. All three split a problem into smaller pieces, but they differ in how subproblems relate and in how the final choice is made.
| Paradigm | Subproblems | Choice strategy | Typical example |
|---|---|---|---|
| Dynamic programming | Overlapping, stored and reused | Considers all options per state | Edit distance |
| Divide and conquer | Independent, solved separately | Combines results of all parts | Merge sort |
| Greedy algorithm | One remaining subproblem | Commits to the locally best option | Dijkstra’s algorithm |
| Brute force search | Not shared | Enumerates every complete solution | Trying all subsets |
A greedy method is faster when it is provably correct, but it fails on problems such as the 0/1 knapsack, where an early locally attractive choice blocks a better overall solution. Dynamic programming handles those cases because it keeps every relevant alternative until the end.
Designing a dynamic programming solution
A reliable design process starts with a brute-force recursion, then looks for repeated calls with identical arguments. Those arguments become the state. The next step is to check that the state is complete: it must carry every piece of information that affects future decisions, or the stored answers will be wrong.
- Define the state precisely, for example the best value using the first i items with capacity w.
- Write the recurrence and the base cases.
- Choose memoization or tabulation and an evaluation order.
- Estimate states times transition cost before writing code.
- Add reconstruction if the actual solution, not only its value, is needed, by storing choices or backtracking through the table.
The technique appears in many named algorithms: Viterbi decoding in speech and communications, Needleman-Wunsch sequence alignment in bioinformatics, the Floyd-Warshall all-pairs shortest path algorithm and value iteration in reinforcement learning.
Limitations and common mistakes
- State explosion: when the state needs many dimensions or a subset of n items, the table grows to O(2 to the power n) and the method becomes impractical.
- Pseudo-polynomial time: knapsack in O(nW) depends on the numeric value of W, so it is slow when capacities are very large.
- Incomplete state: leaving out a variable that influences later choices produces fast but incorrect answers.
- Wrong evaluation order in tabulation, which reads entries before they are filled.
- Memory limits: a 100,000 by 100,000 table does not fit in memory even if the time is acceptable.
When none of the subproblems repeat, caching adds memory without saving time, and plain divide and conquer is the better choice.
The simple explanation
Dynamic programming means never solving the same small problem twice. You break a big problem into smaller ones. You write down each answer the first time you find it. When the same question comes up again, you look up the answer.
Imagine counting the routes through a city grid. Many routes share the same corners. If you note how many ways lead to each corner, you build the final count quickly. Without notes, you would trace millions of paths one by one.
How it is used in practice
A spell checker needs to suggest corrections for a mistyped word. It measures how close each dictionary word is using edit distance, the minimum number of insertions, deletions and substitutions that turn one word into another.
For a typed word of 10 letters and a candidate of 12 letters, the algorithm fills a table of 11 by 13 cells, where each cell depends only on its three neighbors above and to the left. That is 143 small calculations instead of exploring every possible sequence of edits. Keeping only two rows of the table, the checker compares the input against thousands of candidates in milliseconds and offers the closest matches first.