Dynamic programming

Dynamic programming (DP) rests on two key properties: optimal substructure and overlapping subproblems. Optimal substructure means that an optimal solution to the whole problem can be constructed from optimal solutions to its subproblems. Overlapping subproblems occur when the same subproblem is solved multiple times; DP avoids this by storing solutions in a table (memoization or tabulation).

The technique was formalized by Richard Bellman in the 1950s, who coined the term "dynamic programming" to describe the process of solving problems where decisions are made in stages.¹ Bellman's principle of optimality states that an optimal policy has the property that, regardless of the initial state and decision, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision.

DP can be implemented in two ways: top-down (memoization) and bottom-up (tabulation). In top-down, the problem is solved recursively, and results are cached to avoid recomputation. In bottom-up, subproblems are solved in order of increasing size, typically using an iterative loop and a table.

Both approaches have the same asymptotic complexity, but bottom-up often has lower overhead and avoids recursion depth limits. However, top-down can be easier to implement and only solves subproblems that are actually needed. For example, the Fibonacci sequence can be computed with a simple recursive function, but it becomes exponential without memoization; with DP, it runs in linear time.²

DP is used to solve a wide range of optimization problems. Classic examples include the knapsack problem, longest common subsequence, matrix chain multiplication, and the edit distance between strings. In operations research, DP is applied to inventory management, resource allocation, and shortest path problems (e.g., Bellman-Ford algorithm). In bioinformatics, DP is fundamental for sequence alignment, such as the Needleman-Wunsch and Smith-Waterman algorithms.

In economics, DP is used to model dynamic choices over time, such as optimal consumption and saving, and in control theory for optimal control problems. The versatility of DP stems from its ability to handle problems with a natural ordering of decisions.

Beyond the standard textbook examples, DP has surprising applications. For instance, it is used in speech recognition (via the Viterbi algorithm) and in natural language processing for parsing. In computer graphics, DP is used for seam carving, a content-aware image resizing technique. In finance, DP is used for option pricing, particularly for American options, which can be exercised early.

A lesser-known fact is that Bellman's original work was motivated by multi-stage decision processes in control engineering, and the term "programming" referred to planning, not computer programming. Also, the concept of "dynamic programming" has been applied to problems in game theory, such as finding optimal strategies in stochastic games. Another edge case is that DP can be applied to problems with continuous state spaces using discretization, but this can lead to the curse of dimensionality, where the state space grows exponentially with the number of dimensions.

Several variants of DP exist to handle specific challenges. For example, dynamic programming on trees (tree DP) is used for problems on hierarchical structures, such as finding the maximum independent set in a tree. Another variant is DP with bitmasking, used for problems with small state spaces, such as the traveling salesman problem on small graphs.

In recent years, DP has been combined with machine learning, particularly in reinforcement learning, where the Bellman equation is central to algorithms like Q-learning and value iteration. These methods approximate the value function using function approximators, extending DP to large state spaces. Additionally, there is a growing interest in "differentiable programming" which uses DP-like structures in neural networks, though this is distinct from classical DP.

Optimal substructure

A property of a problem where an optimal solution can be constructed from optimal solutions of its subproblems.

Overlapping subproblems

A situation where the same subproblem is solved multiple times; DP exploits this by storing results.

Memoization

A top-down approach that caches the results of subproblems to avoid recomputation.

Tabulation

A bottom-up approach that fills a table iteratively, solving subproblems in order.

Principle of optimality

Bellman's principle stating that an optimal policy has the property that, regardless of the initial state and decision, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision.