# Feb 13. Dynamic Programming II

All Pairs Shortest Path

Let $A[i][j][k]$ be the shortest path in $G$ (a weighted graph with non-negative edge weights) from $i$ to $j$ that uses only vertices $\{1, 2, 3, \cdots, k\}$. Then we can express $A[i][j][k]$ as $A[i][j][k] = \min \{ A[i][j][k-1], A[i][k][k-1] + A[k][j][k-1]\}$. This is because either the shortest path from $i$ to $j$ using $\{1, 2, 3, \cdots, k\}$ does not use the vertex $k$ at all (thus the term $A[i][j][k-1]$) or it uses the vertex $k$ in which case it only visits $k$ once (since it is a shortest path and the edge weights are non-negative) and hence we get the term $A[i][k][k-1] + A[k][j][k-1]$. Thus one can fill the table $A$ in a bottom up manner giving a running time of $\Theta(n^3)$.

Longest Increasing Subsequence

Given a sequence of integers $s_1, s_2, \cdots, s_n$ find the length of the longest increasing sub-sequence. To apply the dynamic programming paradigm we need to find a table that can be filled efficiently and that gives us the answer. Let $A[j]$ denote the longest subsequence that ends with $s_j$. We can express $A[j]$ as

$A[j] = 1 + \displaystyle\max_{\substack{1\le i < j \\ s_i \le s_j}} \{A[i]\}$

This gives us an $\Theta(n^2)$ algorithm to solve this problem.

Edit Distance

We are given two words $a_1a_2\cdots a_m$ and $b_1b_2\cdots b_n$ and we wish to compute the edit distance between them. The edit distance is defined as the minimum number of insert, delete and replace operations that we need to do to transform the first string into the second. Insert operation allows us to insert a character, delete allows us to delete a character and replace allows us to replace a character with another character.

Let $A[i][j]$ represent the edit distance between $a_1a_2\cdots a_i$ and $b_1b_2\cdots b_j$. Then we may write $A[i][j]$ as

$A[i][j] = \min\{ 1 + A[i-1][j], 1 + A[i][j-1], 1_{a_i\neq b_j} + A[i-1][j-1]\}$

where $1_{a_i\neq b_j}=1$ if $a_i\neq b_j$ and $0$ otherwise. Filling up the table either row wise or column wise gives us an algorithm with running time $\Theta(n^2)$.