= Dynamic programming
{wiki}
= DP
{c}
{synonym}
<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 https://ocw.mit.edu/courses/6-231-dynamic-programming-and-stochastic-control-fall-2015/2beec55b0de261096962e514febe3b5c_MIT6_231F15_Lec2.pdf[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> is
$$
V_i(W)=\begin{cases}
V_{i-1}(W),&W<w_i,\\
\max\{V_{i-1}(W),\ v_i+V_{i-1}(W-w_i)\},&W\geq w_i.
\end{cases}
$$
The 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\geq 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 https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-fall-2011/95e744ee64464cb6bc8f8264faeea080_MIT6_006F11_rec21.pdf[MIT 6.006 knapsack notes, pages 1-3]{ref}; those notes index the remaining items in the opposite direction.
The full computation is small enough to see at once:
$$
\begin{array}{c|rrrrrr}
i\backslash W&0&1&2&3&4&5\\\hline
0&0&0&0&0&0&0\\
1&0&0&3&3&3&3\\
2&0&0&3&4&4&7\\
3&0&0&3&4&5&7
\end{array}
$$
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.
\Image[/knapsack-dynamic-programming.png]
{title=A knapsack table builds the optimal value from smaller subproblems}
{description=The <value function> of this <0-1 knapsack problem> is computed row by row. Outlined entries show the reconstruction of an optimal selection: skip weight 4, take weight 3, then take weight 2. The total weight is 5 and total value is 7.}
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.
\Image[/dynamic-programming-state-dag.png]
{title=Knapsack dependencies and one optimal reconstruction}
{description=Each node is a <dynamic programming state> $(i,W)$ labeled by its <value function>. Arrows point to the earlier-row entries used in the <recurrence relation>, forming a <Directed acyclic graph>. Dashed arrows skip an item; blue arrows take it. The orange <graph path> reconstructs the optimal selection with value 7. Compute in the opposite direction to the arrows, beginning at the zero base row.}
For $n$ items and integer capacity $W\geq1$, 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 https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/7232b0ff982f501556118a8552654762_MIT6_006S20_r19.pdf[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 https://pubsonline.informs.org/doi/10.1287/opre.5.5.723[Bellman, Comment on Dantzig's Paper on Discrete Variable Extremum Problems (1957)].
Back to article page
