Dynamic Programming

Dynamic programming is an algorithm design paradigm that solves problems with optimal substructure and overlapping subproblems by solving each subproblem once and storing its result for reuse, transforming exponential recomputation into polynomial-time computation.

Definition

Dynamic programming is a method that solves an optimization or counting problem by defining its value recursively in terms of overlapping subproblems and computing each distinct subproblem exactly once, caching the result so it can be reused rather than recomputed.

Scope

This topic covers the two hallmarks that make dynamic programming applicable — optimal substructure and overlapping subproblems — and the two implementation styles, top-down memoization and bottom-up tabulation. It includes canonical problems such as the longest common subsequence, edit distance, knapsack, matrix-chain multiplication, and shortest-path dynamic programs, along with state-space design and the analysis of time and space trade-offs. It excludes graph-specific shortest-path methods treated under graph algorithms, though they share the same underlying principle.

Core questions

• Does the problem have optimal substructure that lets an optimal solution be built from optimal sub-solutions?
• How is the set of subproblems (the state space) defined so that each recurs only polynomially many times?
• Should the solution be implemented top-down with memoization or bottom-up with tabulation?
• How can the table be reconstructed to recover the actual optimal solution, not just its value?
• How can space be reduced when only part of the table is needed at each step?

Key concepts

• optimal substructure
• overlapping subproblems
• principle of optimality
• memoization
• tabulation
• state space and recurrence
• longest common subsequence
• edit distance
• knapsack problem

Key theories

Principle of optimality

Bellman's principle of optimality states that an optimal policy has the property that, whatever the initial state and decision, the remaining decisions must constitute an optimal policy for the resulting state — the formal basis of dynamic programming recurrences.

Memoization versus tabulation

A dynamic program can be realized top-down by adding a cache to a recursive formulation (memoization) or bottom-up by filling a table in dependency order (tabulation); both compute each subproblem once but differ in evaluation order and space behavior.

Clinical relevance

Dynamic programming is pervasive in practice: sequence alignment (Needleman-Wunsch, Smith-Waterman) in computational biology, edit distance in spell-checking and version-control diffs, the Viterbi algorithm in speech recognition and communications, and dynamic programs in operations research, finance, and reinforcement learning.

History

Richard Bellman developed dynamic programming in the 1950s while at the RAND Corporation, choosing the name partly to be palatable to research sponsors. The principle of optimality and the Bellman equation became foundational across operations research, control theory and computer science, and the technique was later codified as a core algorithmic paradigm in algorithms textbooks.

Key figures

• Richard Bellman
• Thomas H. Cormen
• Jon Kleinberg
• Éva Tardos

Seminal works

• bellman1957
• cormen2009

Frequently asked questions

What is the difference between divide-and-conquer and dynamic programming?

Both decompose a problem into subproblems, but divide-and-conquer subproblems are independent and solved once, whereas dynamic programming subproblems overlap and would be recomputed many times by naive recursion. Dynamic programming caches subproblem solutions to avoid that recomputation.

When does dynamic programming fail to apply?

It requires optimal substructure and a polynomial-size set of distinct subproblems. If the problem lacks optimal substructure, or if the natural state space is exponential and cannot be compressed, dynamic programming is either incorrect or no longer efficient.