最长公共子序列

• 问题：求两个序列 $X=\{x_1,\dots ,x_m\}$ 和 $Y=\{y_1,\dots ,y_n\}$ 的最长公共子序列（可以不连续）。
• 状态定义：$c[i][j]$ 表示 $X$ 的前 $i$ 个字符和 $Y$ 的前 $j$ 个字符的 LCS 长度。
• 转移方程 (核心)： $c[i][j]=\{\begin{array}{ll}0& i=0\text{ 或 }j=0\\ c[i-1][j-1]+1& i,j>0\text{ 且 }{x}_i=y_j\\ \max (c[i][j-1],c[i-1][j])& i,j>0\text{ 且 }{x}_i\ne y_j\end{array}$
• 复杂度：时间 $O(mn)$。
• 技巧：如果在填表时 $x_i==y_j$，则取左上角值+1；否则取左边或上边的最大值。