Common Subsequence 最大公共字符串

题意：给出两个字符串，求出他们最大的 Common Subsequence。所谓字符串A的 subsequence，就是A所含的字符的一部分或者全部组成的字符串，并且字符的顺序和A中出现的顺序相同。【求两个字符串的最长公共子序列 （LCS）】

思路：这题是简单的动态规划题。

用f [ i ][ j ]表示处理到字符串A的第 i 位 和 字符串B第 j 位时的最大值。
状态转移方程如下：
f [ i ][ j ] = f[ i - 1 ][ j - 1 ] + 1  (A[ i ] == B[ j ])
f [ i ][ j ] = max( f[ i - 1 ][ j ], f [ i ][ j - 1] )    (A[ i ] != B[ j ])
由于每次循环计算只和上一行状态有关
一看就知道要填表，两层循环，o(n2)搞掂

#include
using namespace std;

#define M 5005
#define max(x,y) x>y?x:y
int dp[M][M];
char a[M], b[M];

int main()
{
    int i, j, la, lb;
    while (~scanf ("%s%s", a, b))
    {
        la = strlen (a), lb = strlen (b);
        for (i = 0; i < la; i++)    //边界初始化
            dp[i][0] = 0;
        for (j = 0; j < lb; j++)
            dp[0][j] = 0;
        for (i = 1; i <= la; i++)
        {
            for (j = 1; j <= lb; j++)
            {
                //状态转移
                if (a[i-1] == b[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\n", dp[la][lb]);
    }
    return 0;
}
/*
abcfbc abfcab
4
programming contest
2
abcd mnp
0
*/