动态规划之最长公共子序列算法
算法思想： 假设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 100char 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.outPlease input two sequences numbers: 7 6Please input two sequences:ABCBDABBDCABAThe lowest common subsequence lenght = 4The lowest common subsequence is: B C B A
