Dynamic Programming

Introduction

In the previous section, we explored greedy algorithms, strategies that build solutions by making locally optimal choices at each step. Greedy algorithms are often fast and simple, but they sometimes fail; some problems require us to consider multiple possible choices before we know which is best.

Dynamic programming (DP) breaks a problem into overlapping subproblems and solve each one only once, storing results for reuse. This caching/storing often reduces exponential time to polynomial. Unlike greedy algorithms, DP explores the full space of subproblem solutions rather than committing to a single choice at each step, making it more broadly applicable at the cost of additional time and space.

Types of Dynamic Programming

Top-down (memoization)

This form of DP starts at the “top”, recursively decomposing the problem until hitting the base cases. Results are cached/stored to avoid redundant computation. For example, calculating the $n$th Fibonacci number begins with $fib(n)$, which recurses into $fib(n - 1)$ and $fib(n - 2)$, bottoming out at our base cases $n = 0$ and $n = 1$.

Bottom-up (tabulation)

This form of DP starts at the "bottom", iteratively building up solutions to larger subproblems from smaller ones. We fill a table or array in order, so that each entry is already by the time we need it. For example, when calculating the $n$th Fibonacci number, we start from the bases cases $fib(0) = 0$ and $fib(1) = 1$, then iteratively compute $fib(i) = fib(i - 1) + fib(i - 2)$ for increasing $i$ until we reach $fib(n)$.

General Framework

Dynamic programming encompasses a wide variety of problem types, but most can be solved by working through the same core questions. The following tips and techniques address each one.

1. Identify Subproblems and State

Often, one of the hardest parts of DP is figuring out what a "subproblem" looks like. You should ask yourself: what information do I need to fully describe the state of the problem at any point?

Some common subproblem structures include:

• Including/excluding an element: should I take element $i$ or not?
• Prefix/suffix: optimal solution on the first $i$ elements
• Interval: optimal solution on subarray $[i, j]$
• Remaining capacity: items and budget/weight left (e.g. knapsack)

Once you've identified the subproblem structure, you should make it precise! Write a one/two sentence definition of $OPT(i)$; this forces you to commit to exactly what the subproblem is optimizing, which makes the recurrence much easier to write correctly.

2. Write the recurrence relation and base case

After defining $OPT(i)$, you should ask yourself: how does $OPT(i)$ relate to strictly smaller subproblems? This gives your recurrence. Don't forget to consider all cases (e.g. edge cases, zero capacity)!

Base cases are where the recurrence "bottoms out". You should ask yourself: what is the smallest valid input to your table, and what is the answer there by definition (not by recurrence)?

3. Computation Order

You should compute each subproblem only after all subproblem it depends on. You can determine the dependency direction from your reccurence. Think about which subproblems need to be solved first, and which ones depend on others.

4. Correctness

Prove correctness by strong induction on the subproblem "size" (however you have defined it in your solution). With the inductive structure, first verify that the smallest subproblems are corrctly computed with the base cases. After, assume $OPT(i')$ is correct for all $i' < i$ (inductive hypothesis). Show that the recurrence for $OPT(i)$ produces the correct answer.

5. Runtime

You should analyze the runtime by considering the number of subproblems $\times$ the work per subproblem. In addition, you should consider any precomputations done before filling in the table entries (e.g. computing prefix sums), as well as any steps required for solution reconstruction.

6. Solution Reconstruction

Often, the answer for your DP problem can be found by simply looking into an $OPT$ table value. Other times, you may need to iterate over your table and take the optimum across select entries. Another common pattern for solution reconstruction is backtracking; sometimes, we don't just care about the numerical value of our solution, but rather the steps (for example, after running Bellman-Ford, we might want to return the total cost AND the nodes along the least-cost path). To do this, you should:

• During the forward pass, store a point at each table entry that records which case the recurrence takes.
• Trace back from the final state following these pointers (backtracking from your final solution to recover the path).

Remember to include these steps in your runtime analysis!

Bellman-Ford

Introduction

Consider the single-source shortest path problem: given a weighted directed graph $G=(V,E)$ and a source node $s$, find the shortest path from $s$ to every other vertex. Dijkstra's algorithm solves this greedily, but fails on graphs with negative edge weights. Consider the following graph, where we let our source node be $S$.

If we use Dijkstra's algorithm to find the shortest path from $S$ to $A$, we would greedily select the edge from $S$ to $A$ with weight $2$ and be done. However, we observe that the least cost path is $S \rightarrow B \rightarrow A$ (total cost $5 + (-4) = 1$).

This failure of Dijkstra's algorithm motivates the Bellman-Ford algorithm, which handles negative edge weights by reformulating shortest paths as a DP problem. We add the constraint that the input graph $G$ has no negative weight cycles (otherwise there is no shortest path, as we could repeatedly take the cycle path to lower our overall cost).

The Algorithm

We first observe that any shortest path in the graph with $n = |V|$ nodes uses at most $n - 1$ edges. A simple path cannot repeat vertices; a non-sample path would contain a cycle, which either has positive cost (and can be removed) or negative cost (contradicting our negative-cost cycle assumption).

We define the subproblem $OPT(i, v)$ to be cost of the shortest path from source node $s$ to $v$ using at most $i$ edges. The previous observation gives us a finite bound $(n - 1)$ on the number of edges any shortest path can use.

Our base cases are $OPT(0, s) = 0$ and $OPT(0, v) = \infty$ for all $v \ne s$ (impossible to reach node $v \ne s$ using $0$ edges). For our recurrence, the shortest path can use at most $i - 1$ edges (no change), or it arrives at $v$ via some edge $(u, v)$ using at most $i - 1$ edges to reach $u$:

$$\begin{align*} OPT(i, v) = \min\left(OPT(i - 1, v), \min_{(u, v) \in E} \left[ OPT(i - 1, u) + w(u, v) \right] \right) \end{align*}$$

To fill out the table, we can fill it out for each of the $n - 1$ rounds, iterating through each node to update its minimum-path cost. We output $OPT(n - 1, v)$ for all $v$ as our final answer.

The table has dimensions $n \times |V|$, so there are $O(n \cdot |V|)$ cells to fill. The cost per cell isn't $O(1)$; to compute $OPT(i, v)$, we take the minimum over all incoming edges to $v$, which varies by vertex. If we sum the work across all vertices in a single round $i$:

$$\begin{align*} \sum_{v \in V} \deg(v) = O(|E|) \end{align*}$$

since each edge $(u, v) \in E$ contributes one or two computations (depending on an undirected or directed graph) for nodes $u$ and $v$. Since we drop constants, each round requires $O(|E|)$ work, giving a total time complexity of $O(|V| \cdot |E|)$.

Bellman-Ford DP Visualizer

Initialize base case

The base case sets the source distance to 0 before any edges are used.

Step 1 / 16

dp[i][v] = min(dp[i - 1][v], min(dp[i - 1][u] + w(u, v)))

Full DP table

Row 0 initializes s to 0 and every other entry to ∞. Later rows fill in as the simulation progresses.

i	s	a	b	c
0	0	-	-	-
1	-	-	-	-
2	-	-	-	-
3	-	-	-	-

Segmented Least Squares

Introduction

Given points in the plane, we often want to describe their trend by fitting a line. The classic least squares line has a clean closed form of minimizing the squared distance between points and the line, but a single line isn't always a good model: data that rises, levels off, then climbs again is captured far better by a sequence of line segments.

This creates a tradeoff. More segments always lower the total error (with $n$ point and $n - 1$ segments connecting each consecutive pair of points, our squared error is zero), but such a fit just memorizes the data. We want few segments and low error at the same time. The segmented least squares problem formalizes and solves this balance.

For points $(x_1, y_1), \dots, (x_n, y_n)$ and a line $L : y = ax + b$, the least squares error is the sum of squared vertical distances:

$$\text{Error}(L) = \sum_{i = 1}^{n} \left(y_i - a x_i - b\right)^2.$$

Setting the partials with respect to $a$ and $b$ to zero gives the minimizing line in closed form:

$$a = \frac{n \sum_i x_i y_i - \left(\sum_i x_i\right)\left(\sum_i y_i\right)}{n \sum_i x_i^2 - \left(\sum_i x_i\right)^2}, \qquad b = \frac{\sum_i y_i - a \sum_i x_i}{n}.$$

The main takeaway from this is that for any group of points, the minimum single-line error can be computed quickly.

We are given points $P = \{(x_1, y_1), \dots, (x_n, y_n)\}$ with $x_1 < \dots < x_n$. A solution partitions them into contiguous segments, fitting one line per segment. Writing $e(S)$ for the minimum single-line error on segment $S$, and charging a fixed penalty $C > 0$ per segment, the cost of a partition is

$$\sum_{\text{segments } S} e(S) \; + \; C \cdot (\text{number of segments}).$$

Design a polynomial time algorithm to find a partition minimizing this cost. Observe that having large $C$ favors a coarse fit, while small $C$ tolerates more segments. In addition, the brute force algorithm requires trying all $2^n - 1$ partitions, which is far too slow.

The Algorithm

Let $p_i$ refer to point $(x_i, y_i)$. Consider the last point $p_n$. It sits in some segment, which (by contiguity) must be $p_i, \dots, p_n$ for some $i \le n$. Once we fix where that segment starts, the points $p_1, \dots, p_{i-1}$ form an independent instance of the same problem. That substructure gives the DP relation.

Let $e_{i,j}$ be the minimum single-line error on $p_i, \dots, p_j$, and let $\text{OPT}(j)$ be the optimal cost for the first $j$ points. We try every possible starting point $i$ for the final segment:

$$\text{OPT}(j) = \min_{1 \le i \le j} \Big( e_{i,j} + C + \text{OPT}(i-1) \Big), \qquad \text{OPT}(0) = 0.$$

We fill in the table from $j = 1, \dots n$, and output $\text{OPT}(n)$ as our answer. To recover the segments, store the argmin $i$ at each $j$ and trace back from $n$.

Precomputing all $e_{i,j}$: there are $O(n^2)$ pairs, and with prefix sums of $x_k$, $y_k$, $x_k y_k$, $x_k^2$, each error is an $O(1)$ lookup, so we take $O(n^2)$ time for the precomputations. Filling the table costs $O(j)$ per entry, which again $O(n^2)$ across all $n$ OPT entries. Thus, the overall runtime of our algorithm is $O(n^2)$.

Knapsack Problem

Introduction

The knapsack problem is a classic dynamic programming example. We have $n$ items with weight $w_i$ and value $v_i$ with an overall weight constraint $W$. We want to select some set of items $S \subseteq \{1, \dots, n\}$ such that the total weight $\sum_{i \in S} w_i \le W$ and the total value $\sum_{i \in S} v_i$ is maximized.

We can't solve this greedily; taking the highest-value items or best value-to-weight ratio first can both lead to suboptimal solutions (often times a combination of smaller, lower-ratio items fits better and gives more total value). This forces us to consider some subsets; however, there are $2^n$ of them. Dynamic programming gives us a way to avoid this exponential blowup by identifying the right subproblem structure.

The Algorithm

We observe that deciding whether to include item $i$ is a binary choice: we either take it or leave it. If we take it, we use $w_i$ of our capacity and gain $v_i$ in value, leaving us with a smaller knapsack on the remaining items. If we choose not to take the item, the problem reduces to the same capacity with one fewer item to consider.

Thus, we let our $OPT[i][w]$ be the max value possible with items $1, \dots, i$ and weight limit $w$. For our base cases, we let $OPT[i][0] = 0$ for all $i$ and $OPT[0][w] = 0$ for all $w$. Intuitively, a weight limit of zero leaves no room for any item, and considering zero items leaves nothing to select; in both cases, the achievable value is 0.

Using our observation, we have two cases to consider in our recurrence $OPT[i][w]$.

• Leave item $i$: item $i$ is not included, so the optimal value is just $OPT[i - 1][w]$, which is the best we can do with the first $i - 1$ items and the same capacity.
• Take item $i$: item $i$ is included, contributing $v_i$ to our value and consuming $w_i$ of our capacity. The remaining capacity $w - w_i$ must be allocated optimally among the first $i - 1$ items, giving $v_i + OPT[i - 1][w - w_i]$. This case is valid when $w_i \le w$.

Taking the better of the two choices, we have the recurrence:

$$\begin{align*} OPT[i][w] = \begin{cases} OPT[i-1][w] & \text{if } w_i > w \\ \max(OPT[i-1][w],\ v_i + OPT[i-1][w - w_i]) & \text{otherwise} \end{cases} \end{align*}$$

To fill out the OPT table, we let our outer loop iterate from $1, \dots, n$ and inner loop iterate from $1, \cdots W$ (this way, each subproblem $OPT[i][w]$ is computed only after $OPT[i - 1][w]$ and $OPT[i - 1][w - w_i]$ are already filled). After filling out the entire table, we output $OPT[n][W]$ as our final answer.

The table has $(n + 1) \times (W + 1)$ entries, each of which are filled in $O(1)$ time using our recurrence (only 1 or 2 choices per table entry). Our total runtime is $O(nW)$.

note

This is a pseudo-polynomial algorithm: it is polynomial in the numeric value of W, but W can be exponential in the number of bits needed to represent it. The algorithm is efficient when $W$ is small, but can be exponentially slow when given a large $W$.

Practice

Problem 1. [Longest Common Subsequence] Given two lists of integers, find the length of their longest common subsequence (LCS). A subsequence is a new sequence derived from an existing sequence by deleting some or all of its elements without changing the relative order of the remaining elements. A common subsequence appears in both subsequences. You don't have to output the LCS, just its length.

Example:

• List A: 3 1 3 2 7 4 8 2
• List B: 6 5 1 2 3 4

The longest common subsequence of lists A and B is 1 2 4 (or 1 3 4), so the answer is 3.

Solution

We use dynamic programming to solve this question. Let the length of list $A$ be $n$ and the length of list $B$ be $m$. We create an $n \times m$ OPT table, where OPT[i][j] represents the longest common subsequence that can be formed using the sequences $a_i, \dots, a_n$ and $b_j, \dots, b_m$.

For any $i > n$ or $j > m$, let $OPT[i][j] = 0$. We construct our OPT table using the following relation for $1 \le i \le n$, $1 \le j \le m$.

$$OPT[i][j] = \begin{cases} 1 + OPT[i + 1][j + 1] & \text{if } a_i = b_j \\ \max(OPT[i + 1][j], OPT[i][j + 1]) & \text{otherwise} \end{cases}$$

For our final answer, we output $OPT[1][1]$.

Here is a pseudocode implementation:

initialize (n + 1) x (m + 1) OPT table
Let OPT[n + 1][j] and OPT[i][m + 1] be 0 for all i, j.
for i = n down to 1:
    for j = m down to 1:
        OPT[i][j] = recurrence relation
output OPT[1][1]

Correctness:

Claim: $OPT[i][j]$ equals the length of the longest common subsequence of $a_i, \dots, a_n$ and $b_j, \dots, b_m$.

Proof: By induction on $(n - i) + (m - j)$

Base case: When $i > n$ or $j > m$, at least one of the sequences is empty, so the LCS has length $0 = OPT[i][j]$.

Inductive Step: Let $1 \le i \le n$ and $1 \le j \le m$, and assume the claim holds for all $(i', j')$ with $(n - i') + (m - j') < (n - i) + (m - j)$. In particular, it holds for $(i + 1, j + 1)$, $(i + 1, j)$, and $(i, j + 1)$.

Let $L$ denote the true length of the LCS of $a_i, \dots, a_n$ and $b_j, \dots, b_m$.

Case 1: $a_i = b_j$. We claim $L = 1 + OPT[i+1][j+1]$. By the inductive hypothesis, $OPT[i+1][j+1]$ equals the LCS length of $a_{i+1}, \dots, a_n$ and $b_{j+1}, \dots, b_m$, so $1 + OPT[i+1][j+1]$ is achievable by prepending the match $(a_i, b_j)$. Conversely, any common subsequence of $a_i, \dots, a_n$ and $b_j, \dots, b_m$ has length at most $1 + OPT[i+1][j+1]$, since after optionally matching $a_i$ with $b_j$, the remainder is a common subsequence of $a_{i+1}, \dots, a_n$ and $b_{j+1}, \dots, b_m$. Thus $L = 1 + OPT[i+1][j+1]$.

Case 2: $a_i \neq b_j$. Since $a_i$ and $b_j$ cannot be matched, any common subsequence either excludes $a_i$ or excludes $b_j$ (or both). Therefore $L = \max(L_1, L_2)$, where $L_1$ is the LCS length of $a_{i+1}, \dots, a_n$ and $b_j, \dots, b_m$, and $L_2$ is the LCS length of $a_i, \dots, a_n$ and $b_{j+1}, \dots, b_m$. By the inductive hypothesis, $L_1 = OPT[i+1][j]$ and $L_2 = OPT[i][j+1]$, so $L = \max(OPT[i+1][j], OPT[i][j+1])$.

In both cases, $OPT[i][j] = L$, completing the induction.

Runtime:

To find our solution, we fill in our $n \times m$ sized OPT table. We fill out each entry using our recurrence relation, which takes $O(1)$ time to evaluate. Thus, our overall runtime is $O(mn)$.

Problem 2. [Lunch Selection] David loves sushi! Fortuantely, right outside of his house, there is a restaurant that sells both salmon and tuna rolls. Every day for lunch across $n$ days, he must choose to eat exactly one of the tuna or salmon rolls. He will gain a satisfaction reward $s_i > 0$ for eating a salmon roll and $t_i > 0$ for eating a tuna roll on day $1 \le i \le n$.

Unfortunately, the restaurant's salmon supply is limited, so David refuses to eat salmon on two consecutive days: if he eats a salmon roll on day $i$, he MUST eat a tuna roll on day $i + 1$ (there is no such restriction on tuna). Subject to this constraint, he wants to maximize his total satisfaction $\sum_{r_i(x_i)}$, where $x_i \in \{S, T\}$ is his choice on day $i$, $r_i(S) = s_i$, and $r_i(T) = t_i$.

Given an algorithm that takes as input $s_1, \dots, s_n$ and $t_1, \dots, t_n$ and outputs the maximum total satisfiaction David can achieve subject to the constraint above. Your algorithm should run in $O(n)$ time.

Solution

Subproblems. Let $\text{dp}[i][S]$ be the max total satisfaction over days $1,\dots,i$ given that David eats salmon on day $i$, and $\text{dp}[i][T]$ the max total satisfaction over days $1,\dots,i$ given that he eats tuna on day $i$.

For our recurrence, note that eating salmon on day $i$ forces tuna on day $i-1$:

$$\begin{align*} \text{dp}[i][S] = \text{dp}[i-1][T] + s_i \end{align*}$$

Tuna on day $i$ has no restriction on day $i-1$, so David could have consumed either salmon or tuna:

$$\begin{align*} \text{dp}[i][T] = \max\big(\text{dp}[i-1][S],\ \text{dp}[i-1][T]\big) + t_i \end{align*}$$

We initialize our DP table with base cases $\text{dp}[1][S] = s_1$ and $\text{dp}[1][T] = t_1$. We fill the table by iterating from $i = 1$ up to $i = n$, and output $\max\big(\text{dp}[n][S],\ \text{dp}[n][T]\big)$ as our final answer.

Correctness. Every valid choice sequence corresponds to exactly one path through these states, and each transition enumerates exactly the valid predecessors (salmon only follows tuna; tuna follows either). Since the reward from day $i$ onward depends only on the choice at day $i$, not on the earlier history, optimal substructure holds: an optimal solution restricted to the first $i$ days is itself optimal among sequences ending in that day's choice.

Runtime. Each of the $2n$ states is computed in $O(1)$ from the previous day's two values, so the algorithm runs in $O(n)$ time and $O(1)$ space (since we only need day $i - 1$'s values to compute day $i$'s values, we can simply keep two variables that are overwritten at each iteration). If instead we wanted to reconstruct the sequence of optimal choices David made, we would need to store a full array (which is $O(n)$ space).

Problem 3. [Increasing Subsequence] Given an array of $n$ integers $a_1, \dots, a_n$, determine the longest increasing subsequency in the array, i.e. the longest subsequence where every element is strictly greater than the previous one.

Recall that a subsequence is a sequence that can be derived from an array by deleting some elements without changing the order of the remaining elements.

Output a polynomial time algorithm that finds longest increasing subsequence of an array. If multiple answers exist, output any one of them.

Example: 7 3 5 3 6 2 9 8

The longest increasing subsequence of this array is 3 5 6 9 (other subsequences of length 4 exist).

Solution

For our subproblem, we let $OPT[i]$ be the length of longest increasing subsequence ending with element $a_i$.

For our recurrence, we note that any increasing subsequence ending at $a_i$ is formed by appending $a_i$ to some increasing subsequence ending at an earlier element $a_j$ with $j < i$ and $a_j < a_i$ (the dummy element $a_0$ covers the case where $a_i$ starts a fresh subsequence). We pick the predecessor $j$ maximizing $OPT[j]$:

$$OPT[i] = \max_{0 \le j \le i - 1,\; a_j < a_i} \left( OPT[j] \right) + 1$$

We let our base case be $OPT[0] = 0$ with dummy element $a_0 = \min(a_1, \dots, a_n) - 1$ (this ensures that we can create a new increasing subsequence of length $1$ with each element $a_i$).

$OPT[i]$ is the length of the best increasing subsequence ending at $a_i$, so the length of the overall longest increasing subsequence is

$$\max_{1 \le i \le n} OPT[i].$$

To output an actual subsequence and not just its length (reconstruct the sequence), store the maximizing predecessor for each $i$:

$$\mathrm{prev}[i] = \operatorname*{arg\,max}_{0 \le j \le i-1,\; a_j < a_i} OPT[j].$$

Let $i^\star = \operatorname*{arg\,max}_{i} OPT[i]$. Follow the chain $i^\star,\ \mathrm{prev}[i^\star],\ \mathrm{prev}[\mathrm{prev}[i^\star]],\ \dots$ until reaching the dummy index $0$, collect the real elements, and reverse them.

Running time. We fill $OPT[1], \dots, OPT[n]$ in increasing order of $i$, and each $OPT[i]$ scans all $j < i$, giving $\sum_{i=1}^{n} O(i) = O(n^2)$ total, which is polynomial. Reconstruction adds $O(n)$.

Faster algorithm

The $O(n^2)$ DP already satisfies the polynomial-time requirement, but there is a standard $O(n \log n)$ improvement. Maintain an array $t$ where $t[\ell]$ is the smallest possible tail value among all increasing subsequences of length $\ell$ found so far. For each $a_i$, binary search for the first entry $\ge a_i$ (strict increase) and overwrite it, or append $a_i$ if no such entry exists. The array $t$ stays sorted throughout, and its final length is the LIS length; predecessor pointers recover the subsequence as before.

Problem 4. [Coin Game] Caleb and David play a game with a row of $n$ coins with values $a_1, \dots, a_n$. Players alternate turns, with Caleb going first. On a turn, the current player removes either the leftmost or the rightmost remaining coin and adds its value to their score. Play continues until no coins remain.

Assuming both players play optimally (each maximizes their own final score), give an algorithm that outputs Caleb's final score.

Example: 4 9 1 3

Caleb takes the 3, then David is forced to choose from 4 9 1. Regardless of what David chooses, Caleb gets the 9 on his next turn. Thus, Caleb's optimal score is 12.

Hint

The set of remaining coins is always a contiguous block, so can we index our subproblem by intervals?

Solution

Coming soon!