DP：zoj 1733 || poj 1458 Common Subsequence（最长公共子序列）

【转】http://blog.csdn.net/zxy_snow/article/details/6037072

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <memory.h>
#define MAXLEN 300
using namespace std;
int maxlen[MAXLEN][MAXLEN];
int main(void)
{
 char str[MAXLEN],line[MAXLEN];
 int lens,lenl;
 while(cin >> str)
 {
  memset(maxlen,0,sizeof(maxlen));
  cin >> line;
  lens = strlen(str);
  lenl = strlen(line);
  for(int i=0; i<lens; i++)
   for(int k=0; k<lenl; k++)
    if( str[i] == line[k] )
     maxlen[i+1][k+1] = maxlen[i][k] + 1;
    else
     if( maxlen[i+1][k] > maxlen[i][k+1] )
      maxlen[i+1][k+1] = maxlen[i+1][k];
     else
      maxlen[i+1][k+1] = maxlen[i][k+1];
  cout << maxlen[lens][lenl] << endl;
 }
return 0;
}