동적 계획: 사례 설명

               （        ，             ），        ，       ，                  。

    ：               ，      ，            ，              。

【  】                 
  ，      a[],b[]，         z[]
         ：
    （1）a b         （a[m] == b [n]） ，          ，        z      （“z[0]...z[k-1]” a[m-1] b [n-1]         ）。
    （2） a b          (a[m] != b [n]) ，
     z[k]!=a[m]， “z[0]...z[k-1]” a[m-2] b[n-1]         
     z[k]!=b[m]， “z[0]...z[k-1]” a[m-1] b[n-2]         

            ，
     ab      ，
         a[m] == b [n]          a[m-1] b[n-1]      。
                   （a[m-2] b[n-1]）      L1，   （a[m-1]h b[n-2]）      L2， L1 L2             ，         。

            （       ）
     c[i][j]  a[i] b[j] LCS    
     d[i][j]  c[i][j]           （-1,0,1   、  、     ）
   
    a b        m,n
     a[m] == b[n]，        c[m,n] = c[m - 1, n -1] + 1；（i--，j--）
     a[m] != b[n]， c[m,n] = max{c[m,n - 1], c[m - 1, n]}; ( c[i,j-1]>=c[i-1,j]  j--，  i--；)
      ，i j  index，   m,n  ，      i = 0，j = 0

#include 
#include 
#define MAXLEN 100

void LCSLength(char *x, char *y, int m, int n, int c[][MAXLEN], int b[][MAXLEN])
{
    int i, j;

    for(i = 0; i <= m; i++)
        c[i][0] = 0;
    for(j = 1; j <= n; j++)
        c[0][j] = 0;
    for(i = 1; i<= m; i++)
    {
        for(j = 1; j <= n; j++)
        {
            if(x[i-1] == y[j-1])
            {
                c[i][j] = c[i-1][j-1] + 1;
                b[i][j] = 0;
            }
            else if(c[i-1][j] >= c[i][j-1])
            {
                c[i][j] = c[i-1][j];
                b[i][j] = 1;
            }
            else
            {
                c[i][j] = c[i][j-1];
                b[i][j] = -1;
            }
        }
    }
}

void PrintLCS(int b[][MAXLEN], char *x, int i, int j)
{
    if(i == 0 || j == 0)
        return;
    if(b[i][j] == 0)
    {
        PrintLCS(b, x, i-1, j-1);
        printf("%c ", x[i-1]);
    }
    else if(b[i][j] == 1)
        PrintLCS(b, x, i-1, j);
    else
        PrintLCS(b, x, i, j-1);
}

int main(int argc, char **argv)
{
    char x[MAXLEN] = {"ABCBDAB"};
    char y[MAXLEN] = {"BDCABA"};
    int b[MAXLEN][MAXLEN];
    int c[MAXLEN][MAXLEN];
    int m, n;

    m = strlen(x);
    n = strlen(y);

    LCSLength(x, y, m, n, c, b);
    PrintLCS(b, x, m, n);

    return 0;
}