5. DP

Pseudo-polynomial: an algos running time is polynomial in the numerical value of the input, but not polynomial in the input length (number of bits). If you added one bit, its numerical value would double instead of increase polynomially, which would lead to an exponential runtime.

General DP Template

1. Define the state (subproblem)
2. Define the recurrence
3. Define base cases
4. Choose a computation order
5. Extract the final answer
6. Analyze runtime and space

---

Fibonacci Numbers

Compute the $n$-th Fibonacci number.

State: $F[i]$ = $i$-th Fibonacci number

Base cases: $F[1]=1,F[2]=1$

Recurrence: $F[i]=F[i-1]+F[i-2]$

Runtime: $\mathcal{O}(n)$ Space complexity: $\mathcal{O}(1)$ (store only last two values)

Maximum Subarray Sum (Kadane)

Find the maximum sum over all contiguous subarrays.

State: $R[j]$ = maximum subarray sum ending at index $j$

Base case: $R[0]=0$

Recurrence: $R[j]=\max (A[j],R[j-1]+A[j])$

Extraction: $\max (0,R[n])$

Runtime: $\mathcal{O}(n)$ Space complexity: $\mathcal{O}(1)$

Jump Game (Minimum Jumps)

Minimum number of jumps to reach position $n$.

State: $M[k]$ = farthest index reachable with exactly $k$ jumps

Recurrence: $M[k]=\max \{i+A[i]\mid M[k-1]<i\le M[k]\}$

Extraction: Smallest $k$ such that $M[k]\ge n$

Runtime: $\mathcal{O}(n)$ Space complexity: $\mathcal{O}(1)$

Longest Common Subsequence (LCS)

Length of the longest common subsequence of two strings.

State: $L[i][j]$ = LCS length of prefixes $A[\mathrm{1..}i]$ and $B[\mathrm{1..}j]$

Base cases: $L[i][0]=0,L[0][j]=0$

Recurrence:

• If $a_i=b_j$: $L[i][j]=1+L[i-1][j-1]$
• If $a_i\ne b_j$: $L[i][j]=\max (L[i-1][j],L[i][j-1]$

Runtime: $\mathcal{O}(n\cdot m)$ Space complexity: $\mathcal{O}(n\cdot m)$ (optimizable to $\mathcal{O}(m)$)

Edit Distance (Levenshtein Distance)

Minimum number of insertions, deletions, and substitutions to transform one string into another.

State: $ED[i][j]$ = edit distance between $A[1,\dots ,i]$ and $B[1,\dots ,j]$

Base cases: $ED[i][0]=i,ED[0][j]=j$

Recurrence:

$$ED[i][j]=\min \{\begin{array}{ll}ED[i-1][j]+1& \text{(delete)}\\ ED[i][j-1]+1& \text{(insert)}\\ ED[i-1][j-1]+\text{cost}& \text{(replace / match)}\end{array}$$

where $\text{cost}=0$ if $a_i=b_j$, else $1$.

Runtime: $\mathcal{O}(n\cdot m)$ Space complexity: $\mathcal{O}(n\cdot m)$ (optimizable)

Subset Sum

Determine whether a subset sums to a target value $b$.

State: $T(i,s)$ = whether sum $s$ is achievable using the first $i$ elements

Base cases:

• $T(s,0)=\text{true}$ for all $s$ (can always add to zero)
• $T(0,s)=\text{false}$ for $s>0$ (nothing can never add to a nonzero integer)

Recurrence: $T(i,s)=T(i-1,s)\vee T(i-1,s-A[i])$

Runtime: $\mathcal{O}(n\cdot b)$ (pseudo-polynomial) Space complexity: $\mathcal{O}(n\cdot b)$

Knapsack (0/1 Knapsack)

Maximize total value subject to weight limit $W$.

State: $DP[i][w]$ = maximum value using first $i$ items with capacity $w$

Base cases: $DP[0][w]=0$

Recurrence:

$$DP[i][w]=\{\begin{array}{ll}DP[i-1][w]& \text{if }{w}_i>w\text{ (never fits)}\\ \max (DP[i-1][w],DP[i-1][w-w_i]+v_i)& \text{otherwise}\end{array}$$

where $w_i$ is the weight and $v_i$ the value of the $i$-th item.

Runtime: $\mathcal{O}(n\cdot W)$ Space complexity: $\mathcal{O}(n\cdot W)$ (optimizable to $\mathcal{O}(W)$)

Matrix Chain Multiplication

Example of range DP

Minimize the number of scalar multiplications when multiplying many matrices like $ABCD$ by making use of matrix multiplication’s associativity ($(AB)(CD)$ vs $A(BC)D$ and so on).

State: $DP[i][j]$ = minimum cost to multiply matrices $i$ through $j$

Base case: $DP[i][i]=0$

Recurrence: Try all possible splits:

$$\text{DP}[i][j]=\underset{i\le k<j}{\min }\left(\underset{\text{left matrix}}{\underbrace{\text{DP}[i][k]}}+\underset{\text{right matrix}}{\underbrace{\text{DP}[k+1][j]}}+\underset{\text{combining}}{\underbrace{p_{i-1}\cdot p_k\cdot p_j}}\right)$$

where $p_i$ is the number of cols of the $i$-th matrix (since the num rows must match the number of columns, the $i$-th matrix has dimension $p_{i-1}\times p_i$).

The number of rows after performing matrix mult. always equals the number of rows of the left matrix. The number of cols always equals the number of rows of the right matrix. Since this telescopes:

• $p_{i-1}$: number of rows of the left matrix
• $p_k$: number of cols of left and therefore number of rows of right matrix (dim must match)
• $p_j$: number of cols of right matrix

Calculation order: At the beginning, we only know the cost of multiplying two individual matrices. Therefore, we build up our solution by parenthesizing ever larger groups of matrices. This translates to starting with the diagonal and working upward.

Runtime: $\mathcal{O}(n^3)$ Space complexity: $\mathcal{O}(n^2)$