题意：给出两个序列，求最长公共子序列。
链接： https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1006
思路：
状态转移方程： if(a[i-1] == b[j-1]) dp[i][j] = dp[i-1][j-1] + 1; else dp[i][j] = max(dp[i-1][j], dp[i][j-1]); i，j分别是在a，b字符串中的当前位置，意思是说从0到i和从0到j dp[i][j] 是指当前子序列的最大长度 c[i][j] 是用于判断 如果当前两个恰好相等，则为0，直接输出当前的a或b 如果当前dp[i][j] = dp[i-1][j]，则为1，i-- 同上。 Print（）这里就直接回溯就好了。 回溯路径：走的路径就是图中阴影部分。代码：
#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <algorithm> using namespace std; char a[1010],b[1010]; int dp[1010][1010],c[1010][1010]; char ans[1010]; int lena,lenb; void LCS() { for(int i=1; i<=lena; i++) { for(int j=1; j<=lenb; j++) { if(a[i-1] == b[j-1]) { dp[i][j] = dp[i-1][j-1] + 1; c[i][j] = 0; } else if(dp[i-1][j] >= dp[i][j-1]) { dp[i][j] = dp[i-1][j]; c[i][j] = 1; } else{ dp[i][j] = dp[i][j-1]; c[i][j] = -1; } } } } void print(int i,int j) { memset(ans, 0 ,sizeof ans); int len = 0; while(i && j) { if(c[i][j] == 0) { ans[len++] = a[i-1]; i--; j--; } else if(c[i][j] == 1) i--; else j--; } for(int i = len-1; i>=0; i--) cout << ans[i]; } int main() { while(scanf("%s%s",a,b) != EOF) { lena = strlen(a); lenb = strlen(b); memset(dp, 0,sizeof dp); memset(c, 0,sizeof c); LCS(); print(lena,lenb); cout << endl; } return 0; }