poj 动态规划DP - 1458 Common Subsequence
最长公共子序列。DP经典题目。
两个字符串a与b，dp[i][j]代表在在a的前i个字符与b的前j个字符公共子序列的最大值。
当a的第i个字符与b的第j个字符相等时，最大数等于a的前i-1个字符与b的前j-1个字符最大值+1；否则最大数等于max（a的前i-1个字符与b的前j个字符最大值，a的前i个字符与b的前j-1个字符最大值）。
# include<stdio.h>
# include<string.h>
# define MAX 300
# define max(x,y)(x>y?x:y)
int x[MAX][MAX];
char a[MAX]={0};
char b[MAX]={0};
int main(){
int alen,blen,i,j,t,num;
while(~scanf("%s %s",a,b)){
memset(x,0,sizeof(x));
alen = strlen(a);
blen = strlen(b);
for(i=0;i<alen;i++){
for(j=0;j<blen;j++){
if(a[i] == b[j]) x[i+1][j+1] = x[i][j] +1;
else x[i+1][j+1] = max(x[i+1][j],x[i][j+1]);
}
}
printf("%d\n",x[alen][blen]);
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
}
return 0;
}
智能推荐
注意！
本站转载的文章为个人学习借鉴使用，本站对版权不负任何法律责任。如果侵犯了您的隐私权益，请联系我们删除。