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

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

abcicbaabdkscab

abca

解体思路：

先跑LCS,注意开始的下标。多出来一行一列。其实不用flag[][]数组标记位置，回溯的时候再判断，这道

题也能做，但容易超时，因为需要重新比较，方向也不能完全确定。所以以空间换时间，开辟新的数组

标记，分为3个不同的方向来源，1代表左上，2代表正上，3代表正左，这样倒推求序列的时候方向就

能够唯一确定下来，减少了不必要的比较计算和重新探索。

源代码：

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;char a[1005];char b[1005];char c[1005];//用来保存结果int dp[1005][1005];int flag[1005][1005];int index;void LCS(int len_a, int len_b){ memset(dp,0,sizeof(dp)); memset(flag,0,sizeof(flag)); int i,j; for(i = 1; i <= len_a; i++) { for(j = 1; j <= len_b; j++) { if(a[i - 1] == b[j - 1]) { dp[i][j] = dp[i - 1][j - 1] +1; flag[i][j] = 1; } else if(dp[i][j - 1] > dp[i - 1][j]) { dp[i][j] = dp[i][j - 1]; flag[i][j] = 2; } else { dp[i][j] = dp[i - 1][j]; flag[i][j] = 3; } } }}void getLCS(int n, int m){ while(n>0&&m>0) { if(flag[n][m] == 1) { c[index++] = a[n - 1]; n--; m--; } else if(flag[n][m] == 2) { m--; } else if(flag[n][m] == 3) { n--; } }}void printLCS(){ int i; for(i = index - 1; i >= 0; i--) printf("%c",c[i]); printf("\n");}int main(){ int len_a,len_b; scanf("%s%s",a,b); len_a = strlen(a); len_b = strlen(b); LCS(len_a, len_b); index = 0;//结果的下标 getLCS(len_a, len_b); printLCS(); return 0;}