动态规划之最长公共子序列算法

算法思想：
假设X = (x1, x2, ..., xm), Y = {y1, y2, ..., yn)的最长公共子序列为Z = (z1. z2, ..., zk).
则：
1.若xm = yn, 则zk = xm = yn,且Zk-1是Xm-1和Yn-1的最长公共子序列；
2.若xm != yn, 且zk != xm, 则Z是Xm-1和Y的最长公共子序列；
3.若xm != yn, 且zk != yn, 则Z是X和Yn-1的最长公共子序列。
其中：Xm-1 = (x1, x2, ..., xm-1), Yn-1 = (y1, y2, ..., yn-1), Zk-1 = (z1, z2, ..., zk-1).

c[i][j]存储的是Xi和Yj的最长公共子序列的长度，b[i][j]存储的是c[i][j]的值是由哪一个子问题（如上3个子问题）的解得到的。

#include <stdio.h>

#define MAX 100
char x[MAX+1], y[MAX+1];
int b[MAX+1][MAX+1], c[MAX+1][MAX+1], m, n;

static void init_xy(void);
static void lcs_length(void);
static void lcs(int i, int j);
int main(int argc, char **argv)
{
        init_xy();
        lcs_length();

        printf("The lowest common subsequence is: ");
        lcs(m, n);
        printf("\n");

        return 0;
}

static void init_xy(void)
{
        int i;

        printf("Please input two sequences numbers: ");
        scanf("%d %d", &m ,&n);
        getchar();

        printf("Please input two sequences:\n");
        for(i = 1; i <= m; i++){
                scanf("%c", &x[i]);
        }
        getchar();
        for(i = 1; i <= n; i++){
                scanf("%c", &y[i]);
        }
        getchar();
}

static void lcs_length(void)
{
        int i, j;

        for(i = 1; i <= m; i++){
                for(j = 1; j <= n; j++){
                        if(x[i] == y[j]){
                                c[i][j] = c[i-1][j-1] + 1;
                                b[i][j] = 1;
                        }
                        else if(c[i-1][j] >= c[i][j-1]){
                                c[i][j] = c[i-1][j];
                                b[i][j] = 2;
                        }
                        else{
                                c[i][j] = c[i][j-1];
                                b[i][j] = 3;
                        }
                }
        }
        printf("The lowest common subsequence lenght = %d\n", c[m][n]);
}

static void lcs(int i, int j)
{
        if(i == 0 || j == 0){
                return;
        }

        if(b[i][j] == 1){
                lcs(i-1, j-1);
                printf("%c ", x[i]);
        }
        else if(b[i][j] == 2){
                lcs(i-1, j);
        }
        else{
                lcs(i, j-1);
        }
}

执行结果：


[xxxx@localhost suanfa]$ ./a.out
Please input two sequences numbers: 7 6
Please input two sequences:
ABCBDAB
BDCABA
The lowest common subsequence lenght = 4
The lowest common subsequence is: B C B A