hdu 1159 （最長公共子序列）

//f(i,j)= {f(i-1,j-1)+1 (a[i]==b[j])

 //        max(f(i-1,j),f(i,j-1)) (a[i]!=b[j])

//

//由于f(i,j)隻和f(i-1,j-1), f(i-1,j)和f(i,j-1)有關, 而在計算f(i,j)時, 隻要選擇一個合适的順序, 就可以保證這三項都已經計算出來了, 這樣就可以計算出f(i,j). 這樣一直推到f(len(a),len(b))就得到所要求的解了.

#include<iostream>//2308270 2010-04-07 20:00:44 Accepted 1159 78MS 4216K 692 B C++ 悔惜晟

#include<algorithm>

#include<string>

using namespace std;

int num[1005][1005];

int main()

{

 char str1[1005], str2[1005];

 int i, j, len1, len2;

 while(cin>>str1>>str2)

 {

  memset(num, 0, sizeof(num));

  len1 = strlen(str1);

  len2 = strlen(str2);

  for(i = 1; i <= len1; i++)

   for(j = 1; j <= len2; j++)

   {

    if(str1[i - 1] == str2[j - 1])

     num[i][j] = num[i-1][j-1] + 1;

    else

     num[i][j] = max(num[i-1][j] , num[i][j-1]);

   }

  printf("%d/n", num[len1][len2]);

 }

}