LCS
- 问题
给定序列X=<x1,x2,…,xm>,Y=<y1,y2,…,yj>,求X和Y得最长公共子序列 - 解析
在图中标注得H点中，我们既可以选择左边也可以选择上边，这里我选择了往左走的情况，此时得到的结果为BDE，当然如果H点网上走的话结果就是BCE。
3. 设计
while (~scanf("%s%s", a + 1, b + 1)) {
memset(dp, 0, sizeof(dp));
int i, j;
for (i = 1; a[i]; i++) {
for (j = 1; b[j]; j++) {
if (a[i] == b[j])dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = MAX(dp[i][j - 1], dp[i - 1][j]);
}
}
4. 分析
O（mn）
5.源码
https://github.com/CunHua-YYT/CunHua-YYT/blob/master/LCS.cpp