HDU 1501 Zipper 动态规划经典 (二)

2014-11-24 00:33:30 · 作者: · 浏览: 11
c);
scanf("%s %s %s", str1,str2,str3);
int len1 = strlen(str1);
int len2 = strlen(str2);
int k = 0;
opt[0][0] = 0;

for(int i=1; i<=len2; i++){
if(str2[i-1] == str3[i-1])
opt[0][i] = opt[0][i-1] + 1;
else
opt[0][i] = opt[0][i-1];
}
for( i=1; i<=len1; i++){
if(str1[i-1] == str3[i-1])
opt[i][0] = opt[i-1][0] + 1;
else
opt[i][0] = opt[i-1][0];
}

for( i=1; i<=len1; i++){
for(int j=1; j<=len2; j++){

opt[i][j] = max(opt[i-1][j] + (str1[ i-1 ] == str3[ opt[i-1][j] ]), opt[i][j-1] + (str2[ j-1 ] == str3[ opt[i][j-1] ]) );
//cout << opt[i][j] << " ";
}
}
if(opt[len1][len2] == len1 + len2){
printf("yes\n");
}else
printf("no\n");

}
return 0;
}