算法思想:dp[i][j]记录到A[i],B[j]的位置是Lcs的最大长度,
转移方程:I:dp[i][j]=max(dp[i-1][j],dp[i][j]) (i>1)
II:dp[i][j]=max(dp[i][j-1],dp[i][j]) (j>1)
III:dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1) (A[i]==A[j],i>1,j>1)
处理完后,再从dp[A.length][B.length]处开始回溯找出最大子序列。
代码:
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <cstdlib> using namespace std; char A[100],B[100]; int dp[110][110],cnt; char ans[110]; void ini() { cnt=0; scanf("%s",A); scanf("%s",B); memset(dp,0,sizeof(dp)); memset(ans,'