Codex @codex  0

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).

A greedy-choice property says that some optimal feasible solution contains the locally selected choice. Together with optimal substructure in the remaining instance, it allows repeated commitments. An exchange argument often establishes this property.^[ref]

For interval scheduling, a safe first choice need not belong to every optimal feasible solution. When several optima exist, a commitment may exclude one while retaining another. The useful loop invariant is that the accepted prefix can still be extended to an optimum. Merely keeping the accepted intervals compatible proves feasibility, which is a weaker claim.

Replace sibling leaves in a code tree labelled $a,b$ by their common parent in a rooted tree, now a leaf labelled $m$ of weight $w_m=w_a+w_b$. All other codewords stay fixed; each of $a,b$ loses one bit. For any such code tree $T$ and the contracted code tree $T^{\prime }$, their weighted costs satisfyIf $a,b$ have two least weights, the Huffman sibling property gives an optimal prefix code containing this pair. Its contracted prefix code must be optimal for the reduced weights $w^{\prime }$: any cheaper reduced prefix code could be expanded at $m$ by appending $0,1$, giving a cheaper original prefix code. Conversely, expanding any optimal reduced prefix code adds precisely $w_a+w_b$ and attains the original minimum. This is optimal substructure, the justification for repeating the merge in Huffman coding. ^[ref]

In the exchange diagram, $C,D$ contract to weight $0.3$ at leaf depth in a code tree $2$. The reduced expected codeword length is $0.4\cdot 1+0.3\cdot 2+0.3\cdot 2=1.6$ bits; expanding restores $1.6+0.3=1.9$ bits. For $n=2$, the reduction leaves one symbol: allow its temporary codeword to be empty, of cost zero, so expansion gives the two one-bit codewords. This convention is only the terminal reduced problem; the original source has at least two symbols.

Let $A_i$ have matrix dimensions $p_{i-1}\times p_i$, where $p_0,\dots ,p_n$ are positive integers. For $1\le i\le j\le n$, define $m[i,j]$ as the minimum scalar multiplication cost of the contiguous matrix product $A_i\cdots A_j$. The endpoints $(i,j)$ of an integer interval identify a dynamic programming state. A single matrix needs no matrix multiplication, giving the base case $m[i,i]=0$. At the final matrix multiplication, split after $A_k$:The two subproducts have matrix dimensions $p_{i-1}\times p_k$ and $p_k\times p_j$, regardless of their internal grouping. The recurrence relation adds their optimal costs and the final scalar multiplication cost.^[ref]

Why is this optimal substructure? For a chosen final split $k$, replacing either subproduct's grouping by a cheaper one leaves its matrix dimensions and exact matrix product unchanged, so it decreases the whole cost by the same amount. Therefore an optimal grouping can use optimal groupings on both sides. Conversely, each candidate in the recurrence relation joins two achievable groupings. Mathematical induction on $j-i+1$, starting with the single-matrix base case, proves that the minimum is achievable and no grouping is cheaper.

There are also overlapping subproblems: while evaluating the different final splits of $ABCD$, the cases $A(BCD)$ and $(ABC)D$ both request the cost of $BC$. Recursion without reuse recomputes this answer; memoization or a dynamic programming table stores it once. Fill the table by increasing length $j-i+1$, so both dependencies are ready. Record an attaining split $s[i,j]$ alongside each cost.^[ref]

The dynamic programming table has $n(n+1)/2$ cost entries. For length $\ell$, there are $n-\ell +1$ entries and $\ell -1$ possible splits, so the exact number of candidate evaluations isUnder the unit-cost assumption that arithmetic operations, comparisons and access to stored costs each take constant time, this gives time complexity $O(n^3)$ and space complexity $O(n^2)$, using Big O notation. These bounds concern choosing a grouping from the matrix dimensions; they exclude the subsequent matrix multiplication work. If the dimensions or costs require arbitrarily long integers, their arithmetic and storage costs must also be counted.

Extend the original example by a matrix $D$ with matrix dimensions $3\times 15$, so $(p_0,p_1,p_2,p_3,p_4)=(12,5,40,3,15)$. The Catalan number $C_3=5$ counts all possible groupings. Their scalar multiplication costs areThe optimum is $(A(BC))D$, with cost $1320$. Enumeration makes a useful check here, but dynamic programming reaches the same answer by solving ten integer intervals, including the four single-matrix base cases:For example, $m[2,4]=\min \{1800+5\cdot 40\cdot 15,600+5\cdot 3\cdot 15\}=\min \{4800,825\}=825$. The three final-split candidates for the full matrix product supply a compact certificate:The first candidate already uses the better grouping of $BCD$; the worse $A(B(CD))$ need not be reconsidered at the top level. This is how optimal substructure lets the table represent all five possibilities with only three final candidates.

Read $s[1,4]=3$, which separates $ABC$ from $D$. Then $s[1,3]=1$ separates $A$ from $BC$, and $s[2,3]=2$ separates $B$ from $C$. This recursion stops at every $i=j$, returning the corresponding matrix name. Combining the returned expressions recovers $(A(BC))D$, rather than only its cost. Every recursive call uses a shorter integer interval, establishing algorithm termination; a tied minimum may choose any attaining split. The recovered binary tree has $n$ leaves and $n-1$ internal nodes, so reconstruction takes $O(n)$ steps. Its attraction is the separation between an enormous family of groupings and a small set of reusable dynamic programming states.

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.

A divide-and-conquer algorithm splits an instance into smaller instances of the same kind, solves them recursively, and combines their answers. The smaller instances should be sufficiently smaller to ensure algorithm termination; the combination cost determines whether splitting saves work. The two halves of merge sort illustrate this separation.

Dynamic programming identifies a collection of subproblems and dependencies among them, solves each distinct subproblem once, and stores its answer. A table in dependency order or memoization prevents repeated evaluation of overlapping subproblems. For optimization, an optimal substructure argument justifies constructing an optimal answer from optimal smaller answers.

A greedy algorithm repeatedly makes a locally best feasible choice and commits to it. It avoids exploring alternative continuations. Algorithm correctness therefore needs a greedy-choice property, often proved by replacing the first choice of an optimal solution with the greedy choice without worsening it.

In the coin change problem, take denominations $\{1,3,4\}$ and target amount $6$. The natural greedy algorithm repeatedly chooses the largest denomination not exceeding the remaining amount. It chooses $4$, then $1$, then $1$, for three coins. Yet $3+3=6$ uses only two.

Two is optimal: one coin cannot make $6$ because denomination $6$ is absent, and the displayed pair attains the lower bound. ThereforeThe locally largest first coin loses the possibility of using the better pair of threes. This supplies a concrete failure of the greedy-choice property; optimal substructure alone does not justify the greedy choice. The dynamic programming recurrence from part (b) would compare all feasible first or last denominations and find the pair.

Dynamic programming solves related subproblems once, stores their results, and combines those results in an order consistent with their dependencies. The state must retain all information that determines the remaining choices and their costs. Here an adequate dynamic programming state is the current array index, since future jumps depend only on that index and the fixed input.

The principle of optimality says that the remaining part of an optimal solution must be optimal for the residual problem defined by its state. Equivalently here, the prefix ending at a particular intermediate position of a shortest route must be a shortest route to that position: replacing it by a shorter prefix would shorten the entire route. This is the optimal substructure needed by the dynamic programming recurrence.

Thus $\boxed{\text{store an optimum for each state; combine previously solved states by an optimality recurrence}}$. Overlapping routes share states, so storing results avoids repeatedly solving the same subproblem.

Dynamic programming stores answers to overlapping subproblems so they can be reused. Its optimal substructure requirement, the principle of optimality, says that an optimal answer's remaining subproblem solution must itself be optimal once the final decision and state are fixed.

For global sequence alignment without mismatches, use the two prefix lengths as the state. A final column is either a letter of the first string opposite a gap, a gap opposite a letter of the second, or two equal letters. Removing that column leaves one of three smaller prefix problems. If its alignment were suboptimal, replacing it by a better alignment would improve the whole answer. Many different alignments reach the same prefix state, making reuse valuable. Unequal-letter columns and double-gap columns are forbidden, rather than assigned ordinary finite penalties.

Dynamic programming defines subproblem optima and combines their stored answers through a recurrence. It is useful when optimal substructure and overlapping subproblems allow repeated work to be shared. Several alternative choices can be compared before an optimum is selected.

A greedy algorithm instead commits to a locally selected choice and does not later reconsider it. To be correct, its choice needs a justification such as an exchange argument or a safe-cut property, beyond merely having optimal substructure. Neither method is automatically applicable to every optimization problem. Prim's algorithm illustrates a justified greedy choice; the maximum-segment recurrence below illustrates dynamic programming.

There are three useful distinctions between dynamic programming and a conventional divide-and-conquer algorithm.

These are paradigm-level distinctions, not mutually exclusive definitions: a recursive algorithm can use memoization, and dynamic programming need not be implemented iteratively. For optimization, the dynamic programming state and optimal substructure justify combining stored optimum values; storing repeated work alone does not prove the state is sufficient.

Each physical item may enter neither knapsack or exactly one of them. Let $F_i(a,b)$ be the largest combined value using the first $i$ items with remaining capacity limits $a,b$. Initialize $F_0(a,b)=0$ and computeAn infeasible alternative is omitted. The three alternatives classify the placement of item $i$ exhaustively. Every reference uses row $i-1$, ensuring that no item is placed in both knapsacks. Removing item $i$ from an optimum and applying optimal substructure proves the recurrence relation.

The optimum is $F_n(W_1,W_2)$, with time $O(n(W_1+1)(W_2+1))$, conventionally $O(n{W}_1{W}_2)$ for positive capacities. Two successive layers require $O((W_1+1)(W_2+1))$ space; keep predecessor decisions or recompute them if the actual allocations are wanted. The stipulated uniqueness of values and weights is unnecessary for correctness. The capacity-indexed algorithm is pseudopolynomial.

Use positive integral item weights and a nonnegative integral capacity. For the unbounded knapsack problem, define $K(c)$ to be the best value with total weight at most $c$. ThenThe zero candidate is the empty selection, so unused capacity is allowed and an empty set of fitting items causes no problem. Every nonempty feasible selection has some last item $i$; removing one copy leaves a feasible solution at capacity $c-w_i$. Its value is bounded by the corresponding candidate. Conversely, taking an optimal smaller selection and adding that item attains the candidate, proving the recurrence relation by optimal substructure. Positive weights make every dependency strictly smaller.

Fill capacities in increasing order. There are $W+1$ entries, each scanning $n$ items, so the dynamic programming takes $O(nW)$ time and $O(W)$ storage. A winning item pointer at each capacity reconstructs the chosen multiplicities. These are capacity-dependent, pseudopolynomial bounds. For zero-weight items, any positive value makes the repetition problem unbounded; nonpositive-value zero-weight items may simply be discarded before using the recurrence.

Capacity alone cannot say which items have already been used. For the 0-1 knapsack problem, let $D(i,c)$ use only the first $i$ items, each at most once. ThenThe two alternatives omit item $i$ or take it. In the latter case its remaining companions must solve the smaller problem using the first $i-1$ items; otherwise replacing them would improve the whole selection. Both branches reduce the item index, so taking item $i$ cannot take it again. This establishes the recurrence relation and optimal substructure.

Fill rows in increasing $i$ and return $D(n,W)$. There are $O(nW)$ entries with constant work each. Store the decisions for reconstruction; value-only computation uses $O(W)$ space by keeping two rows, or by scanning capacities downwards in a single row. A forward scan in a single row would instead allow repetitions. Nonnegative integral weights suffice for this version, including zero-weight items, because the item index always decreases.