最长公共子序列

方法1：
--------------------------------------------------------------------------------
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAX(a,b) （ a > b ? a : b）
int main()
{
    int n;
    scanf("%d",&n);
    while (n--)
    {
        char a[1000] = {0}, b[1000] = {0};
        scanf("%s%s",a,b);
        int a_len = strlen(a), b_len = strlen(b);
        int dp[a_len+1][b_len+1];      //定义dp[][]用来记录所有可能的最长公共子序列长度
        memset(dp, 0, sizeof(dp));    //初始化二维数组dp[][];
        int i, j;
        for (i = 1; i <= a_len; i++)    //注意i和j应该从一开始
        {
            for (j = 1; j <= b_len; j++)
            {
                // 如果a[i-1] == b[i-1],则最长公共子序列长度加1
                if (a[i-1] == b[j-1])
                    dp[i][j] = dp[i-1][j-1] + 1;

                //如果a[i-1] != b[i-1],则在两个子问题中去较大值
                else
                    dp[i][j] = MAX(dp[i-1][j], dp[i][j-1]);
            }
        }
        printf("%d\n",dp[a_len][b_len]);
    }
    return 0;
}
--------------------------------------------------------------------------------




方法2：
--------------------------------------------------------------------------------
#include<stdio.h>
#include<string.h>
int MAX(int a, int b, int c)
{
    int t = a;
    if (t > b)
    {
        if (t > c)
            return a;
        else
            return c;
    }
    else
    {
        if (b > c)
            return b;
        else
            return c;
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    while(n--)
    {
        char a[1000],b[1000];
        scanf("%s",a);
        scanf("%s",b);
        int c[100][100]={0};
        memset(c, 0, sizeof(c));
        int i,j;
        int max=0,same;
        for(i=1;i<=strlen(a);i++)
            for(j=1;j<=strlen(b);j++)
            {
                if(a[i-1]==b[j-1])
                    same=1;
                else
                    same=0;
                c[i][j]=MAX(c[i-1][j-1]+same,c[i-1][j],c[i][j-1]);
                if(max<c[i][j])
                    max=c[i][j];
            }
        printf("%d\n",max);
    }
    return 0;
}
--------------------------------------------------------------------------------