最长公共子序列（动态规划）

#define M 10
#define N 10
using namespace std;
int C[M + 1][N + 1];
int B[M + 1][N + 1];
void LCS(int *a, int *b, int m, int n){
    int i, j;
    for(i = 1; i <= m; ++i){
        for(j = 1; j<= n; ++j){
            if (a[i - 1] == b[j - 1]) {
                C[i][j] = C[i - 1][j - 1] + 1;
                B[i][j] = 2;
            } 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] = 3;
                }
            }
        }
    }
}
void Str_Seq(int *a, int m, int n){//倒序输出
    if (m == 0 || n == 0)  return;
    int temp = B[m][n];
    if (temp == 2) {
        cout<<a[m - 1]<<" ";
        Str_Seq(a, m - 1, n - 1);
    } else if (temp == 1) {
        Str_Seq(a, m - 1, n);
    } else {
        Str_Seq(a, m, n - 1);
    }
}

原理参见 屈婉玲老师 算法设计与分析 ORZ