What Is Dynamic Programming?

Dynamic programming is a method for solving optimization problems by breaking them into overlapping subproblems, solving each subproblem once, and storing the results to avoid redundant computation. The technique was formalized by Richard Bellman in the early 1950s at RAND Corporation, and its name was chosen partly for administrative reasons. Its mathematical core is the Bellman principle of optimality: an optimal policy has the property that, regardless of the initial state and decision, the remaining decisions must constitute an optimal policy with respect to the state resulting from the first decision.

The method applies to any problem exhibiting two structural properties. First, the problem must have optimal substructure: an optimal solution to the whole problem contains optimal solutions to its subproblems. Second, subproblems must overlap, meaning the same subproblem reappears in multiple branches of a naive recursive solution. When both properties hold, storing computed subproblem solutions in a table reduces worst-case complexity from exponential to polynomial in many practically important cases.

Optimal Substructure and Memoization

Dynamic programming algorithms are implemented in one of two forms. Top-down memoization begins with the original problem and recurses, caching results as they are computed, so that each subproblem is solved at most once. Bottom-up tabulation fills the table from the smallest subproblems to the largest, eliminating recursion overhead entirely. Both approaches yield the same asymptotic complexity. Classic examples include the computation of shortest paths in weighted graphs (Floyd-Warshall, Dijkstra's single-source variant), sequence alignment in bioinformatics (Smith-Waterman local alignment), and the knapsack problem in combinatorial optimization. The choice of state representation is often the most consequential design decision: a state that captures all information needed to make future decisions is sufficient, but a redundant state inflates the table and the runtime.

Markov Decision Processes

Dynamic programming provides the theoretical and computational foundation for solving Markov decision processes (MDPs), the standard formalism for sequential decision-making under uncertainty. An MDP is defined by a state space, an action space, a transition probability function, and a reward function. The Bellman optimality equations express the value of each state as the maximum expected reward achievable from that state under any policy. Policy iteration and value iteration are two dynamic programming algorithms that solve these equations for finite-state MDPs. Approximate dynamic programming extends these ideas to large or continuous state spaces by replacing exact value functions with parameterized approximations; research on approximate dynamic programming using Bellman residual elimination demonstrates how Gaussian process regression can represent value functions efficiently in continuous domains.

The Viterbi Algorithm

One of the most widely deployed applications of dynamic programming in electrical engineering is the Viterbi algorithm, published by Andrew Viterbi in 1967 for decoding convolutional codes over noisy channels. The algorithm finds the maximum-likelihood state sequence through a trellis by propagating the best partial path to each state at each time step, discarding all inferior paths. It runs in time proportional to the product of the number of states and the sequence length, rather than the exponential cost of exhaustive search. As noted in work on dynamic programming, the Viterbi algorithm, and low-cost speech recognition, the same algorithm applies directly to hidden Markov model decoding, connecting digital communications theory to speech recognition and sequence analysis in a single formal framework.

Applications

Dynamic programming has applications in a range of fields, including:

• Reinforcement learning and deep neural network training, where policy gradient methods and Q-learning build on Bellman equation updates
• Communications and channel coding, where the Viterbi algorithm decodes convolutional and trellis-coded modulation schemes
• Computational biology, where sequence alignment, RNA secondary structure prediction, and phylogenetic inference all rely on DP recursions
• Operations research, where inventory management, resource allocation, and logistics scheduling are solved as finite or infinite-horizon MDPs
• Computer vision and speech processing, where dynamic time warping and HMM decoding find optimal label sequences over time-varying signals