算法1
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <ctime>
using namespace std;
const int N = 1e3+10;
char X[N], Y[N];
int c[N][N], s[N][N];
int n, m;
/*** 分治法的思想
* 把大问题分解成相互独立的小问题,但是会出现类似于斐波那契数列那样的子问题重复计算问题,所以会TLE
* 实现形式: 自顶向下递归
*/
// int LCS(int n, int m)
// {
// if(n==0 || m==0) return 0;
// if(X[n] == Y[m]) return LCS(n-1, m-1)+1;
// else
// return max(LCS(n-1, m), LCS(n, m-1));
// }
/*** 动态规划的思想
* 这里是动态规划的变体形式,与上面的不同之处在于使用c数组来记录子问题的解,
* 避免了重复计算子问题,节省了时间开销,但测试时还是会TLE??。
* 实现形式: 自顶向下递归+备忘录(memo)
*/
// int LCS(int n, int m)
// {
// if(c[n][m] > 0) return c[n][m]; // 不同之处
// if(n==0 || m==0) return 0;
// if(X[n] == Y[m])
// {
// c[n][m] = LCS(n-1, m-1)+1;
// }
// else
// c[n][m] = max(LCS(n-1, m), LCS(n, m-1));
// return c[n][m];
// }
/*** 动态规划的思想
* 这里就是动态规划,问题的最优解根据子问题的最优解来解决,具有最优子结构特性,同时使用c数组记录子问题的最优解,
* 避免了重复计算子问题,节省时间开销,所以上述会TLE是因为递归栈?
* 实现形式: 自底向上的迭代形式
* 这里的s[i][j]记录了X[1..i]和Y[1..j]的子串来源
* if s[i][j] == 1
* 说明X[1..i]和Y[1..j]的子串最后一个字符是X[i] or Y[j]
* elif s[i][j] == 2
* 说明X[1..i]和Y[1..j]的子串最后一个字符是X[1..i-1]和Y[1..j]子串最后一个字符
* elif s[i][j] == 3
* 说明X[1..i]和Y[1..j]的子串最后一个字符是X[1..i]和Y[1..j-1]子串最后一个字符
*/
void LCS(int n, int m)
i
for(int i = 1; i <= n; ++i) c[i][0] = 0;
for(int j = 1; j <= m; ++j) c[0][j] = 0;
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= m; ++j)
{
if(X[i] == Y[j])
{
c[i][j] = c[i-1][j-1]+1; // 斜上方
s[i][j] = 1;
}
else
{
if(c[i-1][j] >= c[i][j-1])
s[i][j] = 2; // 上方
else
s[i][j] = 3; // 左方
c[i][j] = max(c[i-1][j], c[i][j-1]);
}
}
}
}
/***
* 借助s数组输出 X[1..n]和Y[1..m]的LCS
*/
void printsub(int n, int m)
{
if(n==0 || m==0) return ;
if(s[n][m] == 1)
{
printsub(n-1, m-1);
printf("%c", X[n]); // 先输出前X[n-1] Y[m-1]的LCS, 再输出X[n]
}
else if(s[n][m] == 2)
printsub(n-1, m);
else
printsub(n, m-1);
}
int main(void)
{
//X 和 Y的串长
scanf("%d%d", &n, &m);
scanf("%s", X+1); scanf("%s", Y+1);
// printf("%s\n%s\n", X+1, Y+1);
LCS(n, m);
cout<<c[n][m]<<endl;
for(int i = 0; i <= n; ++i)
{
for(int j = 0; j <= m; ++j)
printf("%10d", c[i][j]);
cout<<endl;
}
puts("-------------------------------------------------------------------------------");
for(int i = 0; i <= n; ++i)
{
for(int j = 0; j <= m; ++j)
printf("%10d", s[i][j]);
cout<<endl;
}
printsub(n, m);
return 0;
}