abca
看图，结合代码：
for(i = 1; i <= la; i++){ for(j = 1;j <= lb; j++){ if(a[i] == b[j]){ dp[i][j].num = dp[i-1][j-1].num+1; dp[i][j].fromx = i-1; dp[i][j].fromy = j-1; } else{ if(dp[i-1][j].num > dp[i][j-1].num){ dp[i][j].num = dp[i-1][j].num; dp[i][j].fromx = i-1; dp[i][j].fromy = j; } else{ dp[i][j].num = dp[i][j-1].num; dp[i][j].fromx = i; dp[i][j].fromy = j-1; } } } } #include<iostream> #include<cstdio> #include<cstring> using namespace std; struct node{ int fromx; int fromy; int num; }dp[1005][1005]; int main(){ int i,j,k,la,lb; char a[1005],b[1005],ans[1005]; memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); memset(ans,0,sizeof(ans)); memset(dp,0,sizeof(dp)); scanf("%s%s",a+1,b+1); la = strlen(a+1); lb = strlen(b+1); for(i = 1; i <= la; i++){ for(j = 1;j <= lb; j++){ if(a[i] == b[j]){ dp[i][j].num = dp[i-1][j-1].num+1; dp[i][j].fromx = i-1; dp[i][j].fromy = j-1; } else{ if(dp[i-1][j].num > dp[i][j-1].num){ dp[i][j].num = dp[i-1][j].num; dp[i][j].fromx = i-1; dp[i][j].fromy = j; } else{ dp[i][j].num = dp[i][j-1].num; dp[i][j].fromx = i; dp[i][j].fromy = j-1; } } } } /* for(i = 1;i <= la; i ++){ for(j = 1;j <= lb; j ++){ printf("%d ",dp[i][j].num); } printf("\n"); } */ //printf("la=%d lb=%d i=%d j=%d\n",la,lb,i,j); k=0; i-=1; j-=1; // printf("la=%d lb=%d i=%d j=%d\n",la,lb,i,j); while(dp[i][j].num > 0){ // printf("i=%d j=%d dp[i][j].fromx=%d dp[i][j].fromy=%d\n",i,j,dp[i][j].fromx,dp[i][j].fromy); //printf("dp[i][j].num=%d dp[dp[i][j].fromx][dp[i][j].fromy].num=%d\n",dp[i][j].num,dp[dp[i][j].fromx][dp[i][j].fromy].num); if(dp[i][j].num != dp[dp[i][j].fromx][dp[i][j].fromy].num){ ans[k] = a[i]; k++; } int l1,l2; l1 = i; l2 = j; i=dp[l1][l2].fromx; j=dp[l1][l2].fromy; } for(i=k-1;i>=0;i--) printf("%c",ans[i]); printf("\n"); }