求兩個字符串的公共子序列我們都知道需要使用用動態規劃思想

用res[i][j]表示截止到字符串A的第i個字符串和截止到字符串B的第j個字符的最長公共子序列。如兩個字符串helloworld和loop，res[5][3]表示子串hello和子串loo的最長公共子序列，為lo，長度為2

狀態轉移方程

當i=0或j=0時，res[i][j]=0

當A[i]=B[j]時，res[i][j]= res[i-1][j-1]+1

當A[i]≠B[j]時，res[i][j]= max(res[i][j-1], res[i-1][j])

但是這樣只能算出來最長公共子序列的長度，如果需要輸出子序列的話需要用回溯的方法，比較難。我們可以用一個三維字符型數組來做動態規劃數組，這樣既能得到實際的公共子序列，也能得到長度

定義變量

char s1[105];
char s2[105];
char dp[105][105][105]; // 使用三維dp數組

?具體實現

scanf("%s %s",s1,s2);
int i,j;
int n=strlen(s1);
int m=strlen(s2);
dp[0][0][0] = '\0'; // 初始化為空字符串for(i=1;i<=n;i++){for(j=1;j<=m;j++){if(s1[i-1]==s2[j-1]){strcpy(dp[i][j], dp[i-1][j-1]);int len = strlen(dp[i][j]);dp[i][j][len]=s1[i-1];dp[i][j][len+1]='\0';}else{int L1=strlen(dp[i-1][j]);int L2=strlen(dp[i][j-1]);if(L1>L2)strcpy(dp[i][j], dp[i-1][j]);elsestrcpy(dp[i][j], dp[i][j-1]);}}
}
printf("%d\n",len(dp[n][m]));		//輸出子序列的最大長度
printf("%s\n", dp[n][m]);			//輸出最大子序列