1006 最长公共子序列Lcs + 打印路径

题目链接
给出两个字符串A B，求A与B的最长公共子序列（子序列不要求是连续的）。
比如两个串为：

abcicba
abdkscab

ab是两个串的子序列，abc也是，abca也是，其中abca是这两个字符串最长的子序列。

输入
第1行：字符串A
第2行：字符串B
(A,B的长度 <= 1000)

输出
输出最长的子序列，如果有多个，随意输出1个。

输入样例
abcicba
abdkscab

输出样例
abca

(搬运)视频讲解

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int N = 1e3 + 10;
int len1,len2,la,lb,cur,path[N],dp[N][N];//dp[i][j]表示的是str1的前i个字符,str2的前j个字符的最长公共子序列的长度 
char str1[N],str2[N];
int main(){
    	while(~scanf("%s%s",str1 + 1,str2 + 1)){
    memset(dp,0,sizeof dp);len1 = strlen(str1 + 1);len2 = strlen(str2 + 1);for(int i = 1;i <= len1;i++){
    for(int j = 1;j <= len2;j++){
    if(str1[i] == str2[j])dp[i][j] = max(dp[i][j],dp[i - 1][j - 1] + 1); elsedp[i][j] = max(dp[i][j - 1],dp[i - 1][j]);}}cur = 1,la = len1,lb = len2;while(dp[la][lb]){
    if(dp[la][lb] == dp[la - 1][lb]) la--;else if(dp[la][lb] == dp[la][lb - 1]) lb--;else{
    path[cur++] = la;la--,lb--;} }		for(int i = cur - 1;i >= 1;i--) putchar(str1[path[i]]);}return 0;
}