Dynamic Programming

1. Define (overlapping) subproblems
2. Write down the recurrence that relates subproblems
3. Recognize and solve the base cases

• 1-dimensional DP
• 2-dimensional DP
• Interval DP
• Tree DP
• Subset DP

Let $X$ and $Y$ be the two strings we want to find the length of the $LCS$ of, and $X_i$ $=$ <$X_0$ , $X_1$,..., $X_i$> and $Y_j$ $=$ <$Y_0$, $Y_1$,..., $Y_j$>.

$X_i$ and $Y_j$ are called prefixes of the strings $X$ and $Y$.

Further, let $c[i,j]$ be the length of the optimal $LCS$ of the prefixes $X_i$ and $Y_j$. Then we can have the relation:

$c[i, j]=\left\{\begin{array}{ll}0 & \text { if } i=0 \text { or } j=0 \\ c[i-1][j-1]+1 & \text { if } i, j>0 \text { and } x_{i}=y_{i} \\ \max (c[i, j-1], c[i-1, j]) & \text { if } i, j>0 \text { and } x_{i} \neq y_{j}\end{array}\right.$