Dynamic Programming

5.1 Principles

Dynamic programming (DP) solves problems by:

1. Overlapping subproblems: The same subproblems are solved repeatedly.
2. Optimal substructure: The optimal solution contains optimal solutions to subproblems.

Approaches:

• Top-down (memoisation): Recursive with caching.
• Bottom-up (tabulation): Fill a table iteratively from small subproblems to large.

5.2 Memoisation vs. Tabulation

When to use which:

• Use memoisation when the subproblem space is sparse (not all subproblems are needed).
• Use tabulation when most subproblems are needed (avoids recursion overhead and stack overflow).
• Both achieve the same asymptotic time complexity.

5.3 Optimal Substructure Proof Technique

To prove that a problem has optimal substructure:

1. Show that an optimal solution to the problem includes an optimal solution to a subproblem.
2. Proved by contradiction: if the optimal solution contained a suboptimal sub-solution, replacing it with an optimal one would improve the overall solution.

Example (Shortest Path). If $p$ is a shortest path from $u$ to $v$ and $w$ is an intermediate vertex on $p$Then the subpath of $p$ from $u$ to $w$ is a shortest path from $u$ to $w$.

Proof. If not, there exists a shorter path $p"$ from $u$ to $w$. Then $p'$ concatenated with the subpath of $p$ from $w$ to $v$ would be shorter than $p$Contradicting that $p$ is a shortest path. $\blacksquare$

:::caution Common Pitfall Not all problems have optimal substructure. For example, the longest simple path problem does not: the longest simple path from $u$ to $v$ may not contain the longest simple path from $u$ to an intermediate vertex $w$Because the subpath might share vertices with the rest of the path, creating a non-simple path.

5.4 Common Patterns

1D DP. $dp[i]$ depends on $dp[j]$ for $j < i$. Example: Fibonacci, longest increasing subsequence.

2D DP. $dp[i][j]$ depends on $dp[i'][j']$ for $(i', j')$ in some set. Example: edit distance, Matrix chain multiplication, longest common subsequence.

Interval DP. $dp[i][j]$ depends on $dp[i'][j']$ where $i \leq i' \leq j' \leq j$. Example: Optimal BST, matrix chain multiplication.

5.5 Worked Example: 0/1 Knapsack

Problem. Given $n$ items with weights $w_1, \ldots, w_n$ and values $v_1, \ldots, v_n$And a knapsack of capacity $W$Maximise the total value without exceeding the capacity.

Recurrence:

$dp[i][c] = \begin{cases} 0 & \mathrm{if} i = 0 \mathrm{ or} c = 0 \\ dp[i-1][c] & \mathrm{if} w_i > c \\ \max(dp[i-1][c], dp[i-1][c - w_i] + v_i) & \mathrm{if} w_i \leq c \end{cases}$

Time: $O(nW)$. Space: $O(nW)$ (can be reduced to $O(W)$ with 1D array).

Proof of correctness. For each item $i$Either we don’t include it (value $dp[i-1][c]$) or we include it (value $v_i + dp[i-1][c - w_i]$). The optimal choice is the maximum. The base cases are correct. $\blacksquare$

       c: 0  1  2  3  4  5  6  7
i=0:      0  0  0  0  0  0  0  0
i=1:      0  1  1  1  1  1  1  1
i=2:      0  1  1  4  5  5  5  5
i=3:      0  1  1  4  5  6  6  9
i=4:      0  1  1  4  5  7  8  9

5.6 Worked Example: Edit Distance (Levenshtein Distance)

Problem. Given strings $s$ of length $m$ and $t$ of length $n$Find the minimum number of insertions, deletions, and substitutions to transform $s$ into $t$.

Recurrence:

$dp[i][j] = \begin{cases} j & \mathrm{if} i = 0 \\ i & \mathrm{if} j = 0 \\ dp[i-1][j-1] & \mathrm{if} s[i] = t[j] \\ 1 + \min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) & \mathrm{if} s[i] \neq t[j] \end{cases}$

Where the three cases in the minimum are: delete from $s$Insert into $s$Substitute in $s$.

Time: $O(mn)$. Space: $O(mn)$ (can be reduced to $O(\min(m,n))$).

       ""  s  i  t  t  i  n  g
""       0  1  2  3  4  5  6  7
k        1  1  2  3  4  5  6  7
i        2  2  1  2  3  4  5  6
t        3  3  2  1  2  3  4  5
t        4  4  3  2  1  2  3  4
e        5  5  4  3  2  2  3  4
n        6  6  5  4  3  3  2  3

5.7 Worked Example: Matrix Chain Multiplication

Problem. Given matrices $A_1, A_2, \ldots, A_n$ where $A_i$ has dimensions $p_{i-1} \times p_i$Find the parenthesisation that minimises the total number of scalar multiplications.

Recurrence:

$dp[i][j] = \begin{cases} 0 & \mathrm{if} i = j \\ \min_{i \leq k < j} (dp[i][k] + dp[k+1][j] + p_{i-1} p_k p_j) & \mathrm{if} i < j \end{cases}$

Time: $O(n^3)$. Space: $O(n^2)$.

Proof of correctness. The optimal parenthesisation of $A_i \cdots A_j$ splits at some position $k$: $(A_i \cdots A_k)(A_{k+1} \cdots A_j)$. The cost is the cost of the left subproduct plus the cost of the right subproduct plus the cost of multiplying the resulting matrices ($p_{i-1} \cdot p_k \cdot p_j$ scalar multiplications). The optimal $k$ minimises this total. $\blacksquare$

5.8 Worked Example: Longest Common Subsequence

Problem. Given sequences $X = (x_1, \ldots, x_m)$ and $Y = (y_1, \ldots, y_n)$Find the LCS.

Recurrence:

$dp[i][j] = \begin{cases} 0 & \mathrm{if} i = 0 \mathrm{ or} j = 0 \\ dp[i-1][j-1] + 1 & \mathrm{if} x_i = y_j \\ \max(dp[i-1][j], dp[i][j-1]) & \mathrm{if} x_i \neq y_j \end{cases}$

Time: $O(mn)$. Space: $O(mn)$ (can be reduced to $O(\min(m,n))$ for the length only).

Proof of correctness. If $x_i = y_j$Any LCS of $X[1..i]$ and $Y[1..j]$ must include $x_i$ So $\mathrm{LCS} = 1 + \mathrm{LCS}(X[1..i-1], Y[1..j-1])$. If $x_i \neq y_j$The LCS either Excludes $x_i$ or excludes $y_j$Giving the max of the two subproblems. $\blacksquare$

5.9 Worked Example: Coin Change

Problem. Given coin denominations $d_1, \ldots, d_n$ and a target amount $M$Find the minimum number of coins needed.

Recurrence:

$dp[c] = \begin{cases} 0 & \mathrm{if} c = 0 \\ \min_{i: d_i \leq c}(dp[c - d_i] + 1) & \mathrm{if} c > 0 \end{cases}$

Time: $O(nM)$. Space: $O(M)$.

Proof of correctness. To make change for amount $c > 0$The last coin used must be some $d_i \leq c$. The remaining amount is $c - d_i$And the optimal solution for $c$ uses $1 + dp[c - d_i]$ coins. Taking the minimum over all valid $d_i$ gives the optimal solution. $\blacksquare$

5.10 Worked Example: Longest Increasing Subsequence

Problem. Given a sequence $a_1, \ldots, a_n$Find the length of the longest strictly increasing subsequence (not necessarily contiguous).

Recurrence: $dp[i] = 1 + \max\\{dp[j] : j \lt i \mathrm{~and~} a_j \lt a_i\\}$With $dp[i] = 1$ if no such $j$ exists.

Time: $O(n^2)$. Space: $O(n)$.

:::