Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 38425 Accepted Submission(s): 17634
1 #include<cstdio> 2 #include<cstring> 3 #include<cmath> 4 #include<algorithm> 5 using namespace std; 6 const int Max = 1111; 7 char st1[Max],st2[Max]; 8 int dp[Max][Max]; 9 int main() 10 { 11 while(~scanf("%s %s",st1,st2)) 12 { 13 memset(dp,0,sizeof(dp)); 14 int m=strlen(st1); 15 int n=strlen(st2); 16 for(int i=0;i<m;i++) 17 for(int k=0;k<n;k++) 18 { 19 if(st1[i]==st2[k]) 20 dp[i+1][k+1]=dp[i][k]+1; 21 else 22 dp[i+1][k+1]=max(dp[i+1][k],dp[i][k+1]); 23 } 24 printf("%d\n",dp[m][n]); 25 } 26 return 0; 27 }
hdu-1159 Common Subsequence （dp中的lcs问题）
原文：http://www.cnblogs.com/zmin/p/6858816.html