What Is Dynamic Programming? A Practical Explainer

Dynamic programming is a technique for solving problems by breaking them into smaller, overlapping subproblems, solving each subproblem once, and reusing the stored result whenever it’s needed again — instead of recomputing it from scratch every time. It’s most useful when a naive recursive solution ends up solving the exact same subproblem many times over, which is common enough in optimization and counting problems that dynamic programming shows up constantly in algorithm design, from route planning to text comparison.

The overlapping subproblems that make it worth doing

The classic illustration is computing Fibonacci numbers recursively. The naive definition is simple: fib(n) = fib(n-1) + fib(n-2). But tracing the recursion tree for fib(5) shows the problem: fib(3) gets computed twice, fib(2) gets computed three times, and the redundancy compounds as n grows, producing exponential-time work for a problem with an obviously simpler answer.

Dynamic programming fixes this by storing each subproblem’s answer the first time it’s computed, so later calls that need the same subproblem just look up the cached value instead of recomputing it:

memo = {}

function fib(n):
  if n <= 1: return n
  if n in memo: return memo[n]
  memo[n] = fib(n-1) + fib(n-2)
  return memo[n]

This single change — caching results keyed by the subproblem’s inputs — turns an exponential-time algorithm into a linear-time one. Fibonacci is a toy example, but the same idea scales to genuinely hard problems: shortest paths, string alignment, resource allocation, and scheduling all have dynamic programming formulations that turn otherwise intractable brute-force search into something that runs in polynomial time.

Two ways to apply it: top-down vs bottom-up

Top-down (memoization). Write the natural recursive solution, then add a cache that stores each subproblem’s result the first time it’s solved. This is often the easier version to write, because it follows directly from how you’d naturally express the recursive definition of the problem.

Bottom-up (tabulation). Instead of recursing, build a table of subproblem answers iteratively, starting from the smallest subproblems and working up to the final answer, filling in each entry from ones already computed. This avoids recursion overhead and function call stack depth entirely, and it’s often the version used in performance-sensitive code.

Both approaches compute the same answers using the same underlying subproblem structure; the difference is direction — memoization starts from the top and fills in what’s needed lazily, tabulation starts from the bottom and fills in everything methodically.

When a problem is a dynamic programming candidate

Two properties, together, signal that dynamic programming applies:

• Optimal substructure. The optimal solution to the full problem can be constructed from optimal solutions to its subproblems. If the best route from A to C through B requires the best route from A to B and the best route from B to C, that’s optimal substructure.
• Overlapping subproblems. A naive recursive solution solves the same subproblem repeatedly. If every subproblem in a recursion tree is distinct — no repeats — there’s nothing to cache, and dynamic programming offers no advantage over plain recursion or divide and conquer.

Both conditions need to hold. A problem with optimal substructure but no overlapping subproblems (classic divide-and-conquer problems like merge sort) doesn’t benefit from memoization, because there’s nothing being recomputed to save.

Where it shows up in practice

Dynamic programming isn’t just a textbook exercise — it underlies real infrastructure. Diff tools and version control systems use a dynamic programming algorithm (the longest common subsequence problem) to compute the minimal set of line changes between two file versions. Spell checkers and DNA sequence alignment tools use edit-distance algorithms built the same way. Routing and scheduling systems that need an optimal path or allocation under constraints frequently reduce to a dynamic programming formulation once the problem is framed in terms of subproblems.

It also connects directly to data structure choices: the cache in a memoized solution is usually a hash table when subproblems are keyed by arbitrary values, or a simple array when subproblems are keyed by small integers, as in the Fibonacci example. Choosing the right structure for the memo table matters for the same reasons choosing the right structure matters anywhere else — lookup speed for the cache determines whether the “avoid recomputation” strategy actually pays off. And the trees involved in decomposing some dynamic programming problems relate closely to the recursive structures used in binary search trees, even though the two techniques solve different classes of problems.

The trade-off: time for space

Dynamic programming almost always trades memory for speed — you’re storing every subproblem’s answer so you never compute it twice, which means memory usage grows with the number of distinct subproblems. For problems with a huge subproblem space, this can become the new bottleneck, which is why practical dynamic programming solutions often include a further optimization: discarding cached values that are provably no longer needed, once you know the recurrence only depends on the last few previous results rather than the entire history.

The takeaway

Dynamic programming turns brute-force recursive problems with repeated work into efficient ones by caching each subproblem’s answer the first time it’s solved. It applies specifically when a problem has both optimal substructure and overlapping subproblems — without the second property, there’s nothing to cache and memoization buys you nothing. Recognizing that shape in a problem, whether you implement it top-down with memoization or bottom-up with a table, is often the difference between an algorithm that scales and one that doesn’t.