【noi 2.6_1808】最长公共子序列（DP）

题意：给2个字符串求其最大公共子序列的长度。
解法：这个和一般的状态定义有点不一样，f[i][j]表示 str 前i位和 str2 前j的最大公共子序列的长度，而不是选 str 的第i位和 str2 的第j位。
仔细想想就可以知道只表示“前...”的状态可以保证每次拓展答案时，之前的状态已经保证了“公共”，因此str[i]==str2[j]时f[][]+1也不会错。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std;

const int L=210;
int f[L][L];
char str[L],str2[L];

int mmax(int x,int y) {return x>y?x:y;}
int main()
{
    while (scanf("%s%s",str+1,str2+1)!=EOF)
    {
      int len=strlen(str+1),len2=strlen(str2+1);
      f[0][0]=0;
      for (int i=1;i<=len;i++)
       for (int j=1;j<=len2;j++)
       {
         f[i][j]=mmax(f[i-1][j],f[i][j-1]);
         if (str[i]==str2[j]) f[i][j]=mmax(f[i][j],f[i-1][j-1]+1);
       }
      printf("%d
",f[len][len2]);
    }
    return 0;
}