Dynamic programming

Dynamic programming is a method in mathematical optimization and computer science for solving problems through related subproblems whose results can be reused. Rather than repeatedly evaluating the same possibilities, a dynamic-programming algorithm represents subproblems explicitly and combines their answers according to a recurrence. It supports optimization, counting, and probabilistic inference, as well as sequential decision-making. The method is especially effective when many apparently different solution paths lead to the same subproblem. (ocw.mit.edu)

Origins and mathematical foundations

Richard Bellman developed dynamic programming at the RAND Corporation during the 1950s. His book Dynamic Programming, published in 1957, presented a mathematical framework for multistage decision processes. Here, “programming” refers to planning or selecting decisions, rather than specifically to writing software. The framework extended the range of optimization problems that could be addressed by exploiting their internal structure. (rand.org)

A central idea is Bellman’s principle of optimality: after an initial decision, the remaining decisions must be optimal for the situation resulting from that decision. In algorithmic terms, this is closely associated with optimal substructure, meaning that an optimal solution can be assembled from optimal solutions to appropriately defined subproblems. Overlapping subproblems provide the opportunity for computational savings: the same smaller problem arises repeatedly, so its answer can be stored and reused. (studylib.net)

These properties depend on the chosen formulation. A state must retain all information relevant to subsequent choices. For example, a resource-allocation state may need both the remaining resources and the decisions still available; recording only one of these can produce an invalid recurrence. (ocw.mit.edu)

States, recurrences, and evaluation

Designing a dynamic program involves defining states, expressing their relationships, specifying boundary cases, and determining an evaluation order. A state might describe a prefix of a sequence, a remaining capacity, a graph vertex, or a combination of such quantities. The recurrence specifies how one state’s answer depends on others. In many finite problems, these dependencies form a directed acyclic graph, allowing answers to be calculated after their prerequisites. (live.ocw.mit.edu)

Two common implementations are:

• Top-down memoization: evaluate a recursive formulation as needed, store each computed result, and retrieve it on subsequent requests.
• Bottom-up tabulation: calculate results in a predetermined dependency-respecting order, usually filling an array or table.

Both reuse subproblem answers. Memoization can avoid states never reached from the requested problem, while tabulation makes the evaluation order explicit. Neither approach removes the need to define correct states and base cases. (ocw.mit.edu)

Optimization tables often store only optimal values. To recover the actual decisions, an implementation can also record which transition attained each optimum and then trace these choices backward. When later calculations depend on only a small portion of the table, older entries may be discarded to reduce memory use. (ocw.mit.edu)

Example: the 0–1 knapsack problem

In the 0–1 knapsack problem, each item has a positive integer weight $w_i$ and a value $v_i$. The task is to select items with maximum total value without exceeding capacity $W$, taking each item at most once. Define $D(i,c)$ as the best value attainable using the first $i$ items with capacity $c$. (live.ocw.mit.edu)

With $D(0,c)=0$, the recurrence is

The alternatives exclude or include item $i$. Both refer to the first $i-1$ items, preventing reuse of that item. The requested optimum is $D(n,W)$. This illustrates why remaining capacity belongs in the state: different capacities permit different future selections. (ocw.mit.edu)

The table has $O(nW)$ entries and constant work per entry under standard arithmetic assumptions. Its running time is therefore pseudo-polynomial, not necessarily polynomial in the binary input length: representing $W$ requires only $O(\log W)$ bits. Dynamic programming consequently does not imply that every problem it solves has an efficient polynomial-time algorithm. (ocw.mit.edu)

Sequential and stochastic decisions

For sequential optimization, a value function expresses the best achievable future outcome from a state. A deterministic finite-horizon cost problem can use a Bellman equation of the form

where $a$ is an available action, $c_t$ its immediate cost, and $f_t$ the resulting state. A terminal condition completes the recurrence. Under uncertainty, future costs are replaced by their expected value over possible transitions. (studylib.net)

For a Markov decision process, the Markov property ensures that the current state adequately represents the information needed for future transitions. Value iteration repeatedly applies optimality updates, while policy iteration alternates evaluating a policy with improving its actions. Classical dynamic programming assumes a known transition-and-reward model; many reinforcement learning methods instead estimate related quantities from experience. Cyclic and infinite-horizon models may require repeated updates rather than a single table-filling pass. (incompleteideas.net)

Applications and limitations

Dynamic programming underlies algorithms for shortest paths, sequence comparison, and optimal parenthesization. Edit distance compares string prefixes or suffixes through insertion, deletion, and substitution choices; matrix-chain multiplication selects a parenthesization that minimizes arithmetic work without changing the product. (live.ocw.mit.edu)

In a hidden Markov model, the Viterbi algorithm finds the most probable hidden-state sequence, while the forward algorithm sums over hidden paths to calculate observation likelihoods. These applications show that dynamic programming need not optimize an objective: reusable recurrences can also aggregate probabilities. (web.stanford.edu)

Its main limitation is the number of states and transitions. Multidimensional state spaces can grow rapidly, producing the curse of dimensionality. Reusing results eliminates redundant computation, but cannot by itself make an excessively large state representation tractable. (incompleteideas.net)