作为一个菜鸡，本文作为查询模板
一个序列 S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则 S 称为已知序列的最长公共子序列。
转移方程：
dp[i,j] = 0 i=0 || j=0
dp[i,j] = dp[i-1][j-1]+1 i>0,j>0, a[i] = b[j]
dp[i,j] = max(dp[i-1][j],dp[i][j-1]) i>0,j>0, a[i] != b[j]
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
#include "stdio.h" #define M 10 #define N 8 void printLSC(int i, int j,char *a, int status[][N]){ if(i == 0 || j== 0) return; if(status[i][j] == 0){ printLSC(i-1,j-1,a,status); printf("%c",a[i]); }else{ if(status[i][j] == 1) printLSC(i-1,j,a,status); else printLSC(i,j-1,a,status); } } int main(){ int i,j; char a[M]; char b[N]; scanf("%s",a+1); scanf("%s",b+1); int status[M][N]; //保存状态 int dp[M][N]; for(i = 0; i < M; i++) for(j = 0; j < N; j++){ dp[i][j] = 0; status[i][j] = 0; } for(i = 1; i < M; i++) for(j = 1; j < N; j++){ if(a[i] == b[j]){ dp[i][j] = dp[i-1][j-1] + 1; status[i][j] = 0; } else if(dp[i][j-1] >= dp[i-1][j]){ dp[i][j] = dp[i][j-1]; status[i][j] = 2; } else{ dp[i][j] = dp[i-1][j]; status[i][j] = 1; } } printf("最大长度：%d",dp[M-1][N-1]); printf("\n"); printLSC(M-1,N-1,a,status); printf("\n"); } |
