Luke's Note

題目：http://luckycat.kshs.kh.edu.tw/homework/q111.htm

解法：這題要求出 LCS(最長共同子序列)，故使用 DP(動態規劃) 來解。

注意：這題有個陷阱，要仔細看題目。

#include <stdio.h>

int main()
{
    int num, i, j, temp;
    scanf("%d", &num);

    int s1[num+1], s2[num+1], DPTable[num+1][num+1];

    for(i=1; i<num+1; i++)
    {
        scanf("%d", &temp);
        s1[temp]=i;
    }

    while(scanf("%d", &temp)!=EOF)
    {
        for(i=1; i<num+1; i++)
        {
            /* 因為在 while 的條件式裡，已經先 scanf 第一次了，所以在這邊第一次執行時就不用了。*/
            if(i==1)
            {
                s2[temp]=i;
            }
            else
            {
                scanf("%d", &temp);
                s2[temp]=i;
            }
        }

        for(i=0; i<num+1; i++)
        {
            DPTable[0][i]=0;
            DPTable[i][0]=0;
        }

        for(i=1; i<num+1; i++)
        {
            for(j=1; j<num+1; j++)
            {
                if(s1[i]==s2[j])
                {
                    DPTable[i][j] = DPTable[i-1][j-1]+1;
                }
                else
                {
                    if(DPTable[i-1][j]<DPTable[i][j-1])
                    {
                        DPTable[i][j] = DPTable[i][j-1];
                    }
                    else
                    {
                        DPTable[i][j] = DPTable[i-1][j];
                    }
                }
            }
        }
        printf("%d\n", DPTable[num][num]);
    }
    return 0;
}