Chapter 11: Dynamic Programming Advanced

Let $dp[i][j]$ be the fewest edits turning the first $i$ characters of word1 into the first $j$ characters of word2. Look at how an optimal edit script treats the last characters. If they are equal, nothing is needed and $dp[i][j] = dp[i-1][j-1]$. Otherwise the script either replaces word1[i-1] with word2[j-1], costing $dp[i-1][j-1] + 1$; deletes word1[i-1], costing $dp[i-1][j] + 1$; or inserts word2[j-1] at the end, costing $dp[i][j-1] + 1$. Take the minimum. The base cases $dp[i][0] = i$ and $dp[0][j] = j$ count pure deletions and insertions. Setting them to zero, copied from LCS, makes every answer too small.

The filled table is a map of every alignment. The first row counts up to $n$, inserting all of word2, and the first column counts up to $m$, deleting all of word1. Each interior cell reads three neighbours: diagonal for a match or replacement, above for a deletion, and left for an insertion. So the table is a shortest-path grid in which horizontal and vertical steps cost 1 and a diagonal step costs 0 or 1. Following the minimum from $dp[m][n]$ back to $dp[0][0]$ spells out an optimal edit script. Because each row reads only the one above, two rows of length $n + 1$ are enough when only the distance is needed.

Let $dp[i]$ be the length of the longest strictly increasing subsequence that ends at index $i$. Ending there, the subsequence either consists of $a_i$ alone, length 1, or extends one ending at some earlier $j$ with $a_j < a_i$. So $dp[i] = 1 + \max\{dp[j] : j < i, a_j < a_i\}$, or 1 if no such $j$ exists. Filling left to right works because each entry reads only earlier ones. The inner scan over all $j$ gives $O(n^2)$ time. The LIS can end anywhere, so the answer is $\max_i dp[i]$. Returning $dp[n-1]$ is a common bug, and recovering the subsequence itself needs a parent index for each entry.

The quadratic scan asks, for each element, which earlier subsequences it can extend. Keep less information: let tails[k] be the smallest value that ends any increasing subsequence of length $k + 1$ seen so far. A smaller tail is always better, since more future values can extend it. tails is strictly increasing, so for each new value $x$ binary-search the first entry that is at least $x$. If none exists, append $x$ and the LIS grows by one; otherwise overwrite that entry with $x$. Each step is $O(\log n)$, giving $O(n \log n)$. The length of tails is the answer, but tails itself is generally not a valid subsequence.

Let $dp[i][c]$ be the best value obtainable from the first $i$ items with capacity $c$, where item $i$ has weight $w_i$ and value $v_i$. An optimal packing either leaves item $i$ out, scoring $dp[i-1][c]$, or puts it in, which uses $w_i$ of the capacity and scores $dp[i-1][c - w_i] + v_i$. The second branch is allowed only when $w_i \le c$. Row $i-1$ in both branches is what stops item $i$ from being used twice. With no items the value is zero, so row 0 is all zeros. The table has $(n+1)(W+1)$ cells at $O(1)$ each, which is polynomial in $W$ but exponential in the bits needed to write $W$.

Row $i$ reads only row $i-1$, so the whole table can collapse into one array dp of length $W + 1$. Before item $i$ is processed, dp[c] holds the previous row; the update is dp[c] = max(dp[c], dp[c - w_i] + v_i). The order of the capacity loop now matters. Running $c$ from $W$ down to $w_i$ means dp[c - w_i] is read before this pass has overwritten it, so it still describes packings without item $i$. Running upward reads a value this pass has already updated, one that may already contain item $i$, so the item can be taken again. That silent change turns the code into unbounded knapsack. Space drops from $O(nW)$ to $O(W)$.

With unlimited copies, the state no longer needs to remember which items have been used, only how much capacity remains. Let $dp[c]$ be the best value within capacity $c$. The last item placed can be any item $i$ with $w_i \le c$, and what remains is again an unbounded problem of capacity $c - w_i$, so $dp[c] = \max(dp[c], dp[c - w_i] + v_i)$. In the one-array code this is the 0/1 update with the capacity loop running forwards, from $w_i$ up to $W$: dp[c - w_i] may already include item $i$, which is now allowed. Using the forward loop by accident on a 0/1 problem gives answers that are too large.

Coin change swaps the objective: each coin has value 1 in the count, and we minimise. Let $dp[a]$ be the fewest coins summing exactly to $a$, with $dp[0] = 0$ and every other entry starting at infinity to mean unreachable. For each amount, try every coin $c \le a$ as the last coin: $dp[a] = \min(dp[a], dp[a - c] + 1)$. Filling amounts upward lets each coin be reused. If $dp[A]$ is still infinity, no combination works and the answer is $-1$. Initialising with zero instead of infinity makes impossible amounts look free. Greedy is correct only for special coin systems, so the DP is the safe default.

A reduction answers a new problem by translating it into one we can already solve. If a partition exists, each side sums to $S/2$; conversely, a subset summing to $S/2$ leaves a complement with the same sum. So first reject odd $S$, then ask whether target $= S/2$ is reachable. Let $dp[s]$ be true when some subset of the numbers seen so far sums to $s$, starting from $dp[0] =$ true for the empty subset. For each number $x$, loop $s$ from target down to $x$ and set $dp[s] = dp[s] \lor dp[s - x]$. Descending order keeps each number single-use, exactly as in 0/1 knapsack.

The $O(nS)$ table is fine for small sums, but cheap checks often settle the answer first. If $S$ is odd, return False before allocating anything. If the largest number exceeds $S/2$, it cannot fit on either side, so return False. Once dp[target] becomes true, stop processing further numbers. For speed, store the reachable sums as bits of one integer: bit $s$ set means sum $s$ is reachable, and adding $x$ ORs the integer with a copy of itself shifted left by $x$ bits. One shift updates every sum at once, roughly 64 sums per machine word. None of this changes the worst case, since subset sum is NP-complete, but it makes typical inputs fast.