poj 1458 Common Subsequence ——（LCS）

　　虽然以前可能接触过最长公共子序列，但是正规的写应该还是第一次吧。

　　直接贴代码就好了吧：

#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
const int N = 1000 + 5;

char a[N],b[N];
int dp[N][N];

int main()
{
    while(scanf("%s%s",a+1,b+1) == 2)
    {
        int n = strlen(a+1);
        int m = strlen(b+1);
        memset(dp,0,sizeof dp);
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(a[i] == b[j]) dp[i][j] = dp[i-1][j-1] + 1;
                else dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
            }
        }
        printf("%d
",dp[n][m]);
    }
}