problem :http://acm.hdu.edu.cn/showproblem.php?pid=1159
题目大意:最长公共子序列
思路:经典DP题目,状态方程:dp[i][k]= (1) 0 ,当i或者k为0时; (2) dp[i-1][k-1]+1 当X[i]==Y[k]时。 (3)max{ dp[i-1][k] , dp[i][k-1] },当X[i] != Y[i]时
AC program: #include<iostream> using namespace std; char aa[1002],bb[1002]; int aabb[1005][1005]; int main() { while(scanf("%s%s",aa+1,bb+1)!=EOF) { memset(aabb,0,sizeof(aabb)); int len1=strlen(aa+1); int len2=strlen(bb+1);/// for(int i=1;i<=len1;i++) { for(int k=1;k<=len2;k++)/// { if(aa[i]==bb[k]) aabb[i][k]=aabb[i-1][k-1]+1; else aabb[i][k]=aabb[i-1][k]>aabb[i][k-1]?aabb[i-1][k]:aabb[i][k-1]; } } printf("%d\n",aabb[len1][len2]); } return 0;}