动规，模拟，递推，最长公共子序列

题目链接：http://poj.org/problem?id=1458

解题报告：

1、用二维数组模拟两个字符串上每个子串对应的最长公共子序列。

2、显然，就是要求二维数组最右下的数字

3、递推公式：

if(s1[i-1]==s2[j-1])
    maxlen[i][j]=maxlen[i-1][j-1]+1;
else maxlen[i][j]=max(maxlen[i][j-1],maxlen[i-1][j]);

Memory: 1024KTime: 0MSLanguage: C++Result: Accepted

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

const int MAX=505;
int dp[MAX][MAX]={0};///dp[i][j]表示s1[i]与s2[j]所形成的LCS

int main()
{

    char str1[MAX],str2[MAX];
    while(cin>>str1>>str2)
    {
        int len1=strlen(str1);
        int len2=strlen(str2);
        for(int i=1;i<=len1;i++)
        {
            for(int j=1;j<=len2;j++)
            {
                if(str1[i-1]==str2[j-1])
                    dp[i][j]=dp[i-1][j-1]+1;
                else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        }
        printf("%d
",dp[len1][len2]);
    }
    return 0;
}