学步园

/*This Code is Submitted by Iris for Problem 1227 at 2013-07-26 10:41:29*/
//HOJ 1227 Common Subsequence
//dp[i][j]represents first i elems and first j elems 's LCS
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
int max(int a,int b)
{
    return (a>b)?a:b;
}
int dp[213][213];
int main()
{
    string str;
    while(cin>>str)
    {
        string sub;
        cin>>sub;
//理解DP为什么正确,关键是理解状态转移
//状态转移其实就是分解子问题,分解对了,DP就对了
//分解的时候,只看当前的情况:假设子问题已经算出(因为是按顺序填表格,所以肯定是已经算出)
//+1之后不同的情况状态应该如何转移
//并不是从如何判断特殊情况入手的,这样的话就又陷入了DP所极力避免的东西,
//又去考虑全局而没有将问题的规模降低
        memset(dp,0,sizeof(dp));
        int len1 = str.length(),len2 = sub.length();
        for(int i=1;i<=len1;i++)//其实就是按顺序一行一行填表格O(n^2)复杂度的
        {
            for(int j=1;j<=len2;j++)
            {
                if(str[i-1]==sub[j-1])
                {
                    dp[i][j] = dp[i-1][j-1] + 1;
                }
                else
                {
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        cout<<dp[len1][len2]<<endl;
    }
    return 0;
}