The phrase “dynamic programming” sounds like a piece of software engineering jargon. It is in fact one of the deepest algorithmic ideas of the twentieth century, and its name is a historical accident. Richard Bellman invented the technique at the RAND Corporation in 1953 in the middle of a hostile bureaucratic environment that frowned on the word “research”; he chose a name that sounded harmlessly industrial. The technique itself has nothing to do with programming in the modern sense. It is a mathematical method for taking recursive problems whose naïve solution is exponentially slow and turning them into algorithms whose solution is fast — sometimes shockingly fast. This article is about what dynamic programming actually does, when it works, and why it is so important.
The Fibonacci horror story
Start with the most famous problem in introductory recursion: compute the -th Fibonacci number, defined by , , and for . The recursive definition translates into the most obvious algorithm imaginable:
fib(n):
if n < 2: return n
return fib(n-1) + fib(n-2)
Run this on and you will be waiting a very long time. The reason is that the call tree grows wildly: each invocation of fib(n) spawns two children, and the same subproblems are computed again and again. To get you call and . But computing also requires , and computing recomputes and , which are then recomputed yet again by the other branches. The picture below shows the call tree for ; each gray box is a duplicated subproblem.
The total number of leaves in the tree for is the -th Fibonacci number itself — about where is the golden ratio. So the running time of naïve recursive Fibonacci is exponential in , even though the answer is only one number. This is absurd: any human computing by hand would write down in order, never recomputing the same one twice.
The fix is the entire idea of dynamic programming: remember. Keep a table and fill it in order. Each entry is computed from and in constant time. The total work is , no recursion needed:
fib(n):
T[0] = 0; T[1] = 1
for k from 2 to n: T[k] = T[k-1] + T[k-2]
return T[n]
For the naïve algorithm makes about billion calls; the table-based one makes . The same idea, scaled up, is dynamic programming in its purest form.
The two principles
Dynamic programming applies whenever a problem has two properties.
The first is overlapping subproblems: the recursive structure of the problem causes the same smaller instances to appear many times. Without overlap, there is nothing to memoise. With overlap, storage instead of recomputation pays for itself many times over.
The second is what Bellman called the principle of optimality: an optimal solution to the full problem must contain optimal solutions to its subproblems. The shortest path from to passing through is the shortest from to followed by the shortest from to — not some other path through that happens to do better globally. When this principle holds, you can build an optimal answer bottom-up by stitching together optimal answers to smaller pieces. When it does not, the technique fails — but most natural optimisation problems satisfy it, which is why dynamic programming covers so much ground.
A dynamic-programming algorithm boils down to: identify the right notion of “subproblem”, list the subproblems in an order such that each one only depends on smaller ones, fill in a table by iterating through that order, and read off the answer.
A handful of classical examples
Edit distance. Given two strings and , the edit distance is the minimum number of single-character insertions, deletions, or substitutions needed to turn one into the other. The recursive definition writes in terms of three smaller edit-distance problems on prefixes of and . The naïve recursion is exponential. The dynamic-programming version builds an table in time, filling each cell from its three neighbours to the upper-left. This algorithm is the heart of diff, spell-checking suggestions, plagiarism detection, and DNA-sequence alignment in bioinformatics — three completely different fields, all using the same table.
The 0/1 knapsack problem. Given items with weights and values , and a knapsack of capacity , find the most valuable subset of items that fits. The problem is NP-hard in general, but if is a moderate integer, a dynamic-programming table of size — indexed by “first items considered” and “remaining capacity ” — solves it in time. This is the standard worked example in algorithms classes, and the technique underlies real production planning, financial portfolio optimisation, and resource allocation problems.
Shortest paths. The Bellman–Ford algorithm finds shortest paths in a graph with possibly negative edge weights by iterating a dynamic-programming update for at most rounds. The Floyd–Warshall algorithm computes all-pairs shortest paths by indexing subproblems by “shortest path using only intermediate vertices ” and filling a three-dimensional table. Both are textbook dynamic programming.
Optimal binary search trees and Viterbi decoding in signal processing, CYK parsing in formal language theory, and the forward–backward algorithm for hidden Markov models in statistics are all dynamic-programming algorithms. The technique is one of the most reusable ideas in computer science.
Top-down and bottom-up
There are two stylistic variants of dynamic programming that produce the same answer with different code patterns.
Top-down with memoisation writes the recursive algorithm in the natural way and adds a cache: the first time solve(subproblem) is called, it computes and stores the answer; subsequent calls return the stored value. The recursion structure stays transparent, but the cache may sit on the stack.
Bottom-up tabulation processes the subproblems in dependency order, filling in a table iteratively without explicit recursion. This is typically faster and uses less memory, but you have to work out the right traversal order — which can be tricky for problems with two-dimensional or three-dimensional state spaces.
For Fibonacci both styles are essentially the same, but for harder problems the choice between them can matter. Bottom-up is the workhorse of production code; top-down is the workhorse of clarity.
What it really teaches
Dynamic programming sits at a methodological boundary in computer science. On one side: brute force, “try everything”, combinatorial explosion. On the other side: clever algorithms, mathematical structure, polynomial time. Dynamic programming is the systematic technique for moving a problem across this boundary whenever its subproblems overlap.
The deeper lesson is the principle of optimality itself. Many problems in life and mathematics have the property that optimal global behaviour is built from optimal local behaviour. When this principle holds, you can often replace combinatorial search with structured table-filling; when it does not, you face a fundamentally harder problem. Recognising which side of this line a problem falls on is one of the most useful skills an algorithm designer can develop, and Bellman’s accidental terminology has stuck because the technique it names is genuinely one of the small handful of ideas on which the practical computability of optimisation problems rests.
Bellman built dynamic programming to disguise mathematical research as engineering. Seven decades later, the disguise is irrelevant and the mathematics is everywhere — in compilers, biology, finance, and the basic algorithms course that every computer-science student takes in their first year. Not bad for a name picked to placate a hostile bureaucrat.
Frequently asked
Why is it called 'dynamic programming'?
Because Richard Bellman invented it at the RAND Corporation in the 1950s under a Secretary of Defense — Charles Erwin Wilson — who, in Bellman's words, 'had a pathological fear and hatred of the word research.' Bellman picked a name that sounded like industrial scheduling rather than mathematics. He wrote later: 'I thought dynamic programming was a good name. It was something not even a Congressman could object to.' The name has nothing to do with what the technique actually is — there is no programming language and nothing especially dynamic about it. The real subject is recursion with memory.
What is the principle of optimality?
Bellman's name for the property that makes dynamic programming work. An optimal solution to a problem must contain optimal solutions to its subproblems. In other words, you can build an optimal answer by combining optimal answers to smaller pieces. Shortest paths have this property — the shortest path from A to C that passes through B consists of the shortest path from A to B followed by the shortest from B to C. Many other problems do too. When the principle holds, dynamic programming applies; when it does not, more clever methods are required.
When does dynamic programming actually help?
When a recursive algorithm computes the same subproblem many times. Naive recursion for the n-th Fibonacci number takes exponential time because it recomputes F(k) for small k repeatedly; storing each F(k) the first time you see it brings the cost down to linear. The same speedup applies to edit-distance computations, optimal sequence alignment in bioinformatics, knapsack problems, optimal binary search trees, and many shortest-path computations. The savings can be enormous — from O(2^n) to O(n), or O(n!) to O(n²·2^n) — making the difference between an intractable problem and a routine one.
How is dynamic programming different from divide and conquer?
Both methods break a problem into subproblems, but divide and conquer assumes the subproblems are independent — like merge sort, where the two halves of the array do not share any work. Dynamic programming applies when the subproblems overlap and a clever ordering, or storage, lets each one be solved only once. Divide and conquer is the right tool when the work splits cleanly; dynamic programming is the right tool when the work would otherwise be repeated. The two techniques together cover most of algorithms textbook design.