題意:
給兩個數列,求它們最長相同子數列
解法:
LCS
這邊是用填表來做
程式碼:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX(x,y)( ((x)>(y))?(x):(y) )
int n,m;
int a[123];
int b[123];
int dp[123][123];
int main(){
int i,j;
int Case = 0;
memset(dp,0,sizeof(dp));
while(scanf("%d %d",&n,&m)!=EOF &&(n|m)){
for(i=1;i<=n;++i)scanf("%d",&a[i]);
for(i=1;i<=m;++i)scanf("%d",&b[i]);
for(i=1;i<=n;++i){
for(j=1;j<=m;++j){
if(a[i]==b[j]) dp[i][j] = dp[i-1][j-1]+1;
else dp[i][j] = MAX(dp[i][j-1],dp[i-1][j]);
}
}
printf("Twin Towers #%d\n",++Case);
printf("Number of Tiles : %d\n\n",dp[n][m]);
}
return 0;
}