最長(zhǎng)公共子序列是一個(gè)很經(jīng)典的動(dòng)態(tài)規(guī)劃問題壕探，最近正在學(xué)習(xí)動(dòng)態(tài)規(guī)劃，所以拿來(lái)這里再整理一下郊丛。
這個(gè)問題在《算法導(dǎo)論》中作為講動(dòng)態(tài)規(guī)劃算法的例題出現(xiàn)李请。

動(dòng)態(tài)規(guī)劃，眾所周知厉熟，第一步就是找子問題导盅，也就是把一個(gè)大的問題分解成子問題。這里我們?cè)O(shè)兩個(gè)字符串A揍瑟、B白翻，A = "a0, a1, a2, ..., am-1"，B = "b0, b1, b2, ..., bn-1"。
（1）如果am-1 == bn-1滤馍，則當(dāng)前最長(zhǎng)公共子序列為"a0, a1, ..., am-2"與"b0, b1, ..., bn-2"的最長(zhǎng)公共子序列與am-1的和岛琼。長(zhǎng)度為"a0, a1, ..., am-2"與"b0, b1, ..., bn-2"的最長(zhǎng)公共子序列的長(zhǎng)度+1。
（2）如果am-1 != bn-1巢株，則最長(zhǎng)公共子序列為max（"a0, a1, ..., am-2"與"b0, b1, ..., bn-1"的公共子序列槐瑞，"a0, a1, ..., am-1"與"b0, b1, ..., bn-2"的公共子序列）
如果上述描述用數(shù)學(xué)公式表示，則引入一個(gè)二維數(shù)組c[][]阁苞，其中c[i][j]記錄X[i]與Y[j]的LCS長(zhǎng)度困檩，b[i][j]記錄c[i][j]是通過哪一個(gè)子問題的值求得的，即那槽，搜索方向悼沿。
這樣我們可以總結(jié)出該問題的遞歸形式表達(dá)：

recursive formula

按照動(dòng)態(tài)規(guī)劃的思想，對(duì)問題的求解骚灸，其實(shí)就是對(duì)子問題自底向上的計(jì)算過程糟趾。這里，計(jì)算c[i][j]時(shí)甚牲，c[i-1][j-1]拉讯、c[i-1][j]、c[i][j-1]已經(jīng)計(jì)算出來(lái)了鳖藕，這樣，我們可以根據(jù)X[i]與Y[j]的取值只锭，按照上面的遞推著恩，求出c[i][j]，同時(shí)把路徑記錄在b[i][j]中（路徑只有3中方向：左上蜻展、左喉誊、上，如下圖）纵顾。

flow

C++代碼實(shí)現(xiàn)

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

using namespace std;

void LCS_Print(int **LCS_Direction, char *str, int row, int column)
{
    if(str == NULL)
        return;

    int nLen1 = strlen(str);

    if(nLen1 == 0 || row < 0 || column < 0)
        return;
    
    if(LCS_Direction[row][column] == 1)
    {
        if(row > 0 && column > 0)
            LCS_Print(LCS_Direction, str, row - 1, column - 1);
        printf("%c ", str[row]);
    }
    else if(LCS_Direction[row][column] == 2)
    {
        if(row > 0)
            LCS_Print(LCS_Direction, str, row - 1, column);
    }
    else if(LCS_Direction[row][column] == 3)
    {
        if(column > 0)
            LCS_Print(LCS_Direction, str, row, column - 1);
    }
}

int LCS(char *str1, char *str2)
{
    if(str1 == NULL || str2 == NULL)
        return 0;

    int nLen1 = strlen(str1);
    int nLen2 = strlen(str2);

    if(nLen1 <= 0 || nLen2 <= 0)
        return 0;

    // 申請(qǐng)一個(gè)二維數(shù)組汉额，保存不同位置的LCS值
    int **LCS_Length = new int*[nLen1];
    // 申請(qǐng)一個(gè)二維數(shù)組曹仗，保存公共序列的位置
    int **LCS_Direction = new int*[nLen1];
    for(int i = 0; i < nLen1; i++)
    {
        LCS_Length[i] = new int[nLen2];
        LCS_Direction[i] = new int[nLen2];
    }

    for(int i = 0; i < nLen1; i++)
        LCS_Length[i][0] = 0;
    for(int i = 0; i < nLen2; i++)
        LCS_Length[0][i] = 0;
    
    for(int i = 0; i < nLen1; i++)
    {
        for(int j = 0; j < nLen2; j++)
        {
            LCS_Direction[i][j] = 0;
        }
    }

    cout<<"Init OK!"<<endl;

    for(int i = 0; i <nLen1; i++)
    {
        for(int j = 0; j < nLen2; j++)
        {
            if(i == 0 || j == 0)
            {
                if(str1[i] == str2[j])
                {
                    LCS_Length[i][j] = 1;
                    LCS_Direction[i][j] = 1;
                }
                else
                    LCS_Length[i][j] = 0;
            }
            else if(str1[i] == str2[j])
            {
                LCS_Length[i][j] = LCS_Length[i - 1][j - 1] + 1;
                LCS_Direction[i][j] = 1;
            }
            else if(LCS_Length[i - 1][j] > LCS_Length[i][j - 1])
            {
                LCS_Length[i][j] = LCS_Length[i - 1][j];
                LCS_Direction[i][j] = 2;
            }
            else
            {
                LCS_Length[i][j] = LCS_Length[i][j - 1];
                LCS_Direction[i][j] = 3;
            }
        }
    }

    LCS_Print(LCS_Direction, str1, nLen1 - 1, nLen2 - 1);
    cout<<endl;
    int nLCS = LCS_Length[nLen1 - 1][nLen2 - 1];
    for(int i = 0; i < nLen1; i++)
    {
        delete[] LCS_Length[i];
        delete[] LCS_Direction[i];
    }
    delete [] LCS_Length;
    delete [] LCS_Direction;
    return nLCS;
}

int main()
{
    cout<<LCS("ABCBDAB", "BDCABA")<<endl;
    return 0;
}