Dynamic programming

Dynamic programming solves a mathematical optimization problem by choosing reusable subproblems, recording their value functions, and combining already solved cases through a recurrence relation. Its attraction is that many possible decision histories can share one continuation calculation. A dynamic programming state must retain everything needed to determine the allowed future choices and their rewards. The 0-1 knapsack problem, for example, needs both the available capacity and which items remain available; capacity alone would lose the restriction that each item can be used at most once.

Two ideas explain when this works. Optimal substructure makes an optimal continuation valid inside a larger optimal solution. When subproblems overlap, storing each answer avoids repeated work: memoization computes entries as needed, while a table fills them in dependency order. Start from known base cases. For a problem indexed by increasing size, compute smaller cases first; for a finite sequence of future decisions, work backwards from the terminal reward, as in the Bellman equation. See Bertsekas, MIT lecture 2: optimality and state augmentation.

Consider a 0-1 knapsack problem with item weights $(w_1,w_2,w_3)=(2,3,4)$, item values $(v_1,v_2,v_3)=(3,4,5)$, and capacity $5$. Define the value function $V_i(W)$ to be the largest total item value obtainable from the first $i$ items with total weight at most $W$. Here $i\in \{0,1,2,3\}$ and $W\in \{0,1,2,3,4,5\}$ specify the dynamic programming state. All weights and capacities are nonnegative integers. The empty selection supplies the base case $V_0(W)=0$. The recurrence relation isThe two candidates skip or take item $i$. Both use the previous row, so taking item $i$ cannot take that same item again. The condition $W\ge w_i$ prevents a negative remaining capacity; no entry with $W<0$ is needed. The optimal substructure is concrete: after taking item $i$, its companions must solve the smaller 0-1 knapsack problem on the first $i-1$ items with capacity $W-w_i$. Otherwise replacing them by a better feasible selection would improve the whole selection. Compare ^[ref]; those notes index the remaining items in the opposite direction.

The full computation is small enough to see at once:For example, $V_2(5)=\max \{3,4+3\}=7$ and $V_3(5)=\max \{7,5+0\}=7$. Choosing the feasible item with largest individual value takes weight $4$, earns $5$, and leaves capacity $1$, which cannot fit another item. This greedy algorithm misses the two-item selection of weights $2$ and $3$, whose value is $7$. This example tests the largest-individual-value rule; choosing by value divided by weight happens to find the optimum here.

The number $V_3(5)=7$ is the optimal value, while the choices attaining it form a control policy. To reconstruct one optimal selection, start at $(3,5)$. Equality with $V_2(5)$ allows skipping item $3$. At $(2,5)$, taking item $2$ gives $4+V_1(2)=7$, so continue to $(1,2)$. Take item $1$ and finish at $(0,0)$. In a tie, either maximizing choice suffices to recover one optimum. Recording choices during the calculation or comparing stored entries afterwards recovers the control policy; a final optimal value alone does not describe the selection.

For $n$ items and integer capacity $W\ge 1$, the table uses time complexity $O(nW)$ and space complexity $O(nW)$, counting arithmetic operations and stored numbers using Big O notation. This is pseudo-polynomial time: when weights and capacity use the binary numeral system, the capacity needs only $O(\log (W+1))$ digits. A capacity near $2^b$ creates about $2^b$ columns despite needing only about $b$ digits. Thus this algorithm is practical for moderate capacities but does not establish polynomial time in the encoded input length. See MIT 6.006 recitation 19: knapsack and input size. For the optimal value alone, one array reduces space complexity to $O(W)$: for each item, update capacities in descending order, from $W$ down to $w_i$. Ascending order would read entries already updated for that item and could reuse it. Reconstruction then requires extra information or recomputation.

The link between the knapsack problem and dynamic programming is already explicit in a 1957 paper by Richard Bellman at RAND: its abstract discusses an exact knapsack problem solution using functional equations and cites his 1957 book. See Bellman, Comment on Dantzig's Paper on Discrete Variable Extremum Problems (1957).

For nonnegative maximum jump lengths in an array, let $D[0]=0$ and let unreachable positions have value $\infty$. Classifying a route to $j$ by its penultimate position proves this dynamic programming recurrence. Increasing $j$ is a valid dependency order because every jump advances. Scanning all previous positions uses $\Theta (n^2)$ time complexity and $\Theta (n)$ space complexity. Store a minimizing predecessor to reconstruct a shortest route.

For a directed graph with adjacency matrix $A$, let $D[S,v]$ record whether a path visits precisely the vertices of $S$ once and ends at $v$. The singleton states are true. A larger state is true exactly when some predecessor $u\in S\setminus \{v\}$ has a true state for $S\setminus \{v\}$ and an edge to $v$. Removing or adjoining the last edge proves this recurrence by mathematical induction on $|S|$. There are $n{2}^{n-1}$ states, each requiring at most $n-1$ predecessor checks, giving $O(n^2{2}^n)$ time and $O(n{2}^n)$ storage. A true state for $S=V$ certifies a Hamiltonian path.

After fixing an initial decision in an optimal solution, the remaining decisions must solve the resulting residual problem optimally, with the relevant state and constraints retained. Otherwise substituting a better continuation would improve the original solution. This replacement argument justifies dynamic programming recurrences when the chosen dynamic programming state contains all information needed by future decisions.

An equation expressing the optimum or count for a dynamic programming state in terms of smaller or otherwise previously computable states. A valid dependency order, base cases, and a proof that every candidate solution is represented are required. The minimum coin change recurrence follows by classifying a nonempty solution by its last coin.

Represent a $d$-dimensional box by its side-length vector and allow axis permutations. A box fits another when its permuted dimensions are all strictly smaller. Sorting each vector reduces containment to coordinatewise strict comparison, by the sorted-coordinate criterion for box containment. For an input-order-preserving subsequence, the longest chain ending at position $j$ has one plus the greatest chain length at an earlier fitting position. This last-box decomposition proves the dynamic programming recurrence. Sorting all dimensions and testing all ordered index pairs takes $O(nd\log d+n^{2}d)$ running time. Arbitrary reordering is a different convention, handled by the containment Directed acyclic graph.

Let $a_1\le \cdots \le a_d$ and $b_1\le \cdots \le b_d$ be the separately sorted dimension vectors. Matching corresponding ranks proves the forward construction when every $a_i<b_i$. Conversely, if $a_k\ge b_k$, then the $d-k+1$ source dimensions from rank $k$ onward require distinct targets strictly larger than $a_k$, but only the last $d-k$ target ranks could qualify. The pigeonhole principle rules out such a permutation. Strict inequality matters: equal side lengths do not fit under this convention. Sorting and checking gives an $O(d\log d)$ decision algorithm.

Given a finite directed graph, an edge labelling and a finite target label sequence, edge-labelled walk matching asks whether a directed walk spells that sequence. Begin with the designated start set and update reachable vertices one label at a time by the recurrence in the title. Appending a final matching edge proves the invariant by induction. Repeated vertices are allowed; a requirement of a vertex-simple directed path is a different problem and can encode Hamiltonian path. Scanning all edges and clearing a vertex layer costs $O(k(|V|+|E|))$ for $k$ labels.

Attach nonnegative edge scores to edge-labelled walk matching. For each layer and endpoint, keep the greatest product over matching prefixes. Only edges with the required current label enter the maximum. Multiplication by a nonnegative score preserves order, proving the dynamic programming recurrence. Store a predecessor for each reachable layer entry to recover a maximizing walk. A reachable score of zero must be distinguished from no matching walk: keep reachability separately or use an impossible negative sentinel and skip it before multiplication. The score is the defined product; interpreting it as a physical event probability can require extra independence assumptions.

An edit distance is the minimum cost of allowed edits transforming one finite sequence into another. With unit insertion, deletion and substitution costs, the prefix table has boundaries $D[i,0]=i$, $D[0,j]=j$ and recurrence $D[i,j]=\min (D[i-1,j]+1,D[i,j-1]+1,D[i-1,j-1]+[x_i\ne y_j])$. The last alignment action gives one of these cases; appending that action to an optimal shorter alignment proves the converse inequality. Thus induction proves the recurrence, yielding $O(mn)$ running time for nonempty input lengths $m,n$. Two rolling rows suffice when only the distance is required; retaining predecessor actions supports reconstruction.

For positive integer weights of total $S=3h$, store reachable pairs $(x,y)$ of sums assigned to the first two groups after each input list prefix. The third sum is determined by the processed total minus $x+y$. Assign each new occurrence to one of the three groups using a fresh layer; accept exactly final state $(h,h)$. The transitions are sound by construction and complete by deleting the last occurrence from a valid assignment. The state range is $0\le x,y\le h$, giving $O(n(h+1{)}^2)$ time and $O((h+1{)}^2)$ rolling space.

Given ordered words $w_1,\dots ,w_n$ and a target $s$, minimise the number of words in an order-preserving subsequence whose concatenation is $s$. Let $D(i,j)$ be the optimum using the first $i$ words to produce the first $j$ symbols. Either skip $w_i$, or, when it matches the target suffix ending at $j$, take it and add one to $D(i-1,j-|w_i|)$. The state records both the available-word boundary and target progress, preventing reuse or reordering of words. For $|s|=O(n)$ and bounded word length, this is an $O(n^2)$-time algorithm with straightforward predecessor reconstruction.

A form of value iteration that writes each updated state value immediately, so later updates in the same sweep can use the new value.

An algorithm that uses dynamic programming: it computes and stores solutions to overlapping subproblems, then combines them through a recurrence relation.

For an integer $p\ge 2$ and $k\ge 0$, unlimited denominations $1,p,\dots ,p^k$ admit optimal greedy algorithm. In a minimum-count solution, no smaller denomination can occur $p$ times: carrying those stamps to the next denomination reduces their count by $p-1$. Thus all counts below the maximum are base-$p$ digits, whose total value is at most $p^k-1$. The maximum-denomination count is forced to be the quotient on division by $p^k$, and repeating the argument forces every greedy remainder step.

For positive integer denominations, the coin change problem asks for coins summing to a target amount $v$; this recurrence minimizes their number. With unlimited supply, use the recurrence in the title, $M[0]=0$, and $\infty$ for an unreachable amount. Classifying a solution by its last coin proves the recurrence by induction. Recording that coin reconstructs an optimum. The table uses $O(nv)$ running time and $O(v)$ space complexity; this is a pseudopolynomial time bound.

If each available coin can be used only once, update $M[t]\leftarrow \min (M[t],1+M[t-x_i])$ for amounts in descending order for each coin. Descending order retains the previous row's value at $t-x_i$ and prevents reuse. Ascending order instead permits repeated use of the current coin. The distinction is a dependency invariant, not a cosmetic loop-order choice.

For denominations $1$ and $c_j=2^j+1$ with $0\le j\le k$, greedy minimizes coin count. Among optimal representations choose a lexicographically maximal descending denomination-count vector. Two unit coins can be replaced by one two; two $c_j$ below the largest can be replaced by $c_{j+1}+1$ without increasing count but improving that vector. Thus all smaller denominations occur at most once. For the coins below $c_j$, write their value as $L=B+r$, where $r$ is their count and $B\le 2^j-1$ is the sum of their distinct power-of-two parts. If $L\ge c_j$, one $c_j$ and $L-c_j$ units use $L-2^j\le r-1$ coins, contradicting optimality. Therefore the residual below each denomination is smaller than it, forcing precisely the greedy quotients.

A method for counting or weighting configurations by processing successive slices and recording only the information that crosses the current boundary. Compatible boundary states define a matrix of transitions, so repeated slices can be handled by matrix powers. It is especially useful when the boundary is much smaller than the whole configuration.

Count or sum integers by processing their numerical digits and merging prefixes that have the same possible continuations. Typical state records include the current position, whether the prefix still equals an upper limit, a remainder, or a bit mask of digits already used. The final answer comes from accepting exactly those states satisfying the desired digit constraints.

A dynamic programming method that advances a boundary across a structured object and records only the information needed on that boundary. For tilings by pieces of bounded height, a bit mask recording occupied cells in a few frontier rows can determine every legal continuation. Its state space is typically exponential in the width but independent of the total height.

Count multisets of allowed positive coin values whose sum is a target. Initialize $w(0)=1$ and $w(s)=0$ for $s>0$. For each coin $c$, update $w(s)\leftarrow w(s)+w(s-c)$ in increasing order of $s\ge c$. The outer loop over coins counts each multiset once while allowing repeated use of a coin.

A dynamic programming state is an element of a state space that summarizes all information needed for a remaining mathematical optimization problem. Histories can share a value function entry only when their allowed continuations and future rewards agree, or have the same conditional laws in a stochastic control problem. Time or the remaining item index may be part of the summary. If past decisions still affect feasibility or rewards, enlarge the dynamic programming state; forgetting those effects invalidates the Bellman equation.

Optimal substructure means that the relevant parts of an optimal solution solve their own subproblems optimally. For a 0-1 knapsack problem, removing a chosen item leaves an optimal selection among the other allowed items at the reduced capacity. For sequential mathematical optimization, this becomes the dynamic programming principle: after fixing the next decision and resulting dynamic programming state, use an optimal continuation. Optimal substructure justifies the recurrence relation; overlap between subproblems explains why storing a value function can save work.

An optimal value over a time interval is the supremum of immediate reward plus the conditional optimal continuation value. For a controlled state $X$ and running reward $\ell$, this reads $J(x,t)={\sup }_a\mathbb{E}[{\int }_t^{t+h}\ell (X_s,a_s,s)ds+J(X_{t+h},t+h)\mid X_t=x]$, under the usual admissible concatenation and information conditions. Conditioning and concatenating strategies proves both inequalities: every strategy's continuation is bounded by the value function, while approximately optimal continuations approach that bound. For a smooth diffusion value function, Itô formula and the limit $h\downarrow 0$ yield the Hamilton-Jacobi-Bellman equation.

An average-reward optimal policy maximizes long-run expected reward per time step. In a finite recurrent Markov chain, a stationary policy's gain is its expected one-step reward under the stationary distribution. Initial-state effects are encoded by a bias function rather than by the gain. In a communicating finite control problem, the average-reward Bellman equation certifies a policy that is optimal from every initial state.

The gain $g$ and bounded bias $h$ in this equation give an upper bound on average reward for every policy: summing its action inequalities telescopes the bias, leaving total expected reward at most $ng+h(i)-\mathbb{E}h(X_n)$. A stationary maximizing action at each state attains equality and hence the gain $g$. Policy improvement computes the current gain and bias, then switches to actions with greater reward-plus-expected-bias value.

A control policy selects admissible actions using only the information available at each time, possibly with randomization. General policies may depend on the whole observed history. Nonanticipation and measurability are part of admissibility in a controlled Markov process.

A Markov policy uses only the current state and, in the nonstationary case, the current time. A stationary Markov policy has the form $u_t=u_{\ast }(X_t)$ for one measurable selector $u_{\ast }$. It is a restricted class of control policies, whose sufficiency for an optimization problem requires the appropriate dynamic-programming hypotheses.

If a successful step in action $i$ has expected reward $a_i\ge 0$ and survival probability $q_i=1-p_i$, a finite-horizon retirement problem with zero wealth after capture has threshold ${\max }_i{a}_i{q}_i/p_i$. Above it, induction makes retirement optimal; below it, a single further step already beats retirement. The threshold does not depend on the remaining positive horizon.

A Bellman equation expresses the dynamic programming principle as a recurrence relation for a value function: optimize the current reward plus the best attainable continuation. Let $s$ be a dynamic programming state, $A_t(s)$ the allowed actions at time $t$, $r_t(s,a)$ the immediate reward, and $F_t(s,a)$ the next dynamic programming state. With terminal time $T$ and terminal reward $g$, the deterministic finite-horizon Bellman equation isHere $V_t(s)$ measures total reward from time $t$ through the terminal reward. Start with $g$ and evaluate backwards; the terminal condition anchors the recurrence relation. For finite nonempty action sets, finite rewards, and finite terminal rewards, a maximum exists at each step. If an optimum need not be attained, use a supremum. A minimization problem instead uses a minimum or infimum. The 0-1 knapsack problem above is the same comparison between an immediate item value plus a continuation and the continuation after skipping. See Bertsekas, MIT lecture 2: the backwards recursion.

In a Markov decision process, the next dynamic programming state $S_{t+1}$ is random. If $r_t(s,a)$ denotes the expected immediate reward and $\beta$ is a discount factor, the finite-horizon Bellman equation becomesThe conditional expectation averages over the next dynamic programming state before choosing the current action; that action cannot use a future outcome that has not yet been observed. For a finite state space with transition probabilities $p_t(s^{\prime }\mid s,a)$, the continuation term is $\beta {\sum }_{s^{\prime }}{p}_t(s^{\prime }\mid s,a)V_{t+1}(s^{\prime })$. Taking $\beta =1$ gives the undiscounted finite-horizon problem. With a discount factor $0\le \beta <1$, rewards $k$ steps ahead carry a factor ${\beta }^k$, including the terminal reward. A maximizing action for each $(t,s)$ specifies a Markov policy, which contains decisions rather than just optimal scores.

For an infinite horizon with a finite state space, finite nonempty action sets, time-independent transition probabilities, bounded rewards $|r(s,a)|\le M$, and a discount factor $0\le \beta <1$, the optimal value function satisfiesIn this setting the maximizing dynamic programming operator is a contraction mapping in the supremum norm, so the Banach fixed-point theorem gives a unique bounded fixed point and convergence of repeated application to it. See Bertsekas, MIT lecture 15: bounded discounted problems. These hypotheses matter: with one state, one action, zero reward, and $\beta =1$, the Bellman equation is merely $V(s)=V(s)$, so every finite constant is a fixed point, although the actual total-reward value function is zero. The average-reward Bellman equation and Hamilton-Jacobi-Bellman equation address other settings with their own conditions.

For a finite Markov decision process under fixed policy $\pi$, bounded reward vector $r^{\pi }$ and $0\le \gamma <1$, splitting the discounted return at its first step gives $V^{\pi }=r^{\pi }+\gamma P^{\pi }{V}^{\pi }$. A stochastic matrix has supremum-norm operator bound one, so ${\sum }_{k\ge 0}(\gamma P^{\pi }{)}^k$ converges and $V^{\pi }=(I-\gamma P^{\pi }{)}^{-1}{r}^{\pi }$. This is policy evaluation, not optimization over actions.

The operator $T^{\pi }V=r^{\pi }+\gamma P^{\pi }V$ performs one exact fixed-policy backup. Since each row of $P^{\pi }$ averages component differences, $\Vert T^{\pi }V-T^{\pi }U{\Vert }_{\infty }\le \gamma \Vert V-U{\Vert }_{\infty }$. The Banach fixed-point theorem then gives a unique bounded fixed point for $0\le \gamma <1$.

This one-step operator combines immediate cost with optimized discounted continuation. It is monotone. For nonnegative costs, iterating it from zero produces increasing finite-horizon values bounded above by the infinite-horizon value. If a nonnegative fixed point has a minimizing measurable selector, repeated conditional expectation and dropping the nonnegative terminal value show that the corresponding stationary policy costs no more than that fixed point. Thus the infinite-horizon value, when the Bellman equation holds, is the least nonnegative fixed point.

For nonnegative rewards, a nonnegative value satisfying the maximizing Bellman equation dominates every competing policy, even for $\beta \ge 1$. Iterate the one-step inequality, discard the nonnegative terminal value, then apply the monotone convergence theorem to the accumulated reward.

The Hamilton--Jacobi--Bellman equation is the continuous-time Bellman equation. For state dynamics $\dot{x}=f(x,u,t)$, running cost $L(x,u,t)$ and terminal cost $\Phi (x)$, a smooth value function satisfies

For a nonnegative classical solution $V$ of a finite-horizon Hamilton-Jacobi-Bellman equation with nonnegative running reward $r$, the process $V(X_t,t)+{\int }_0^{t}r(X_s,a_s)ds$ is a local supermartingale under every admissible control. The Itô formula gives nonpositive drift because the chosen control cannot exceed the supremum in the equation. Stop where the stochastic integral becomes a true martingale, take expectations and apply the Fatou lemma. Nonnegativity prevents loss of a lower bound when removing the stops, giving the verification upper bound. A maximizing control attains the bound when its stopped reward processes are uniformly integrable.

A linear-quadratic optimal-control problem has linear state dynamics and running and terminal costs defined by quadratic forms. Its value function is quadratic in the state, the optimal feedback is linear, and its coefficient obeys a Riccati equation.

A backward scalar or matrix recurrence for the quadratic coefficients in a value function for a linear-quadratic optimal control problem. It results from completing the control square in the Bellman equation. Multiplicative noise modifies the quadratic coefficients through its second moments.

A value function assigns each dynamic programming state and time the best objective function value attainable over the remaining decisions. It is a score, whereas a control policy specifies the actions producing that score. In the 0-1 knapsack problem above, $V_3(5)=7$ is the score, and choosing the items of weights $2$ and $3$ attains it. In sequential mathematical optimization, the Bellman equation computes a value function by comparing immediate reward plus continuation value. Use a supremum or infimum when the best score need not be attained by any admissible control policy.

At a point where $\varphi (b)$ is finite, this is an affine plane supporting the epigraph from below: $\varphi (u)\ge \varphi (b)+{\lambda }^T(u-b)$ for every $u$. A nonzero coefficient of the vertical coordinate permits normalization to the displayed graph form. For a constrained value function, the slope is exactly an attained multiplier in the Strong Lagrangian property. When the value function is differentiable at an interior point of its finite domain, a supporting slope equals its gradient: apply the supporting inequality along both positive and negative multiples of each coordinate direction and take limits.

A hidden object lies in box $i$ with posterior probability $p_i$. Searching box $i$ costs $c_i$ and, conditional on the object being there, detects it with probability ${\alpha }_i$. After an unsuccessful search of box $i$, Bayes' theorem updates the probabilities to

When search continues until discovery, expected search cost is minimized by searching at each step a box maximizing ${\alpha }_i{p}_i/c_i$. An adjacent-interchange argument compares two searches: placing $i$ before $j$ costs less exactly when ${\alpha }_i{p}_i/c_i\ge {\alpha }_j{p}_j/c_j$.

If discovery in box $i$ earns reward $R_i$ and stopping earns zero, the Bellman equation isIf ${\sum }_i{c}_i/({\alpha }_i{R}_i)<1$, every posterior state has some $i$ with ${\alpha }_i{p}_i{R}_i>c_i$, so stopping is never optimal.