β£

- Define (overlapping) subproblems
- Write down the recurrence that relates subproblems
- 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.$

β£

β£

β£

β£

β£

β£

β£

β£

04-dynamic-programming.pdf171.6KB