动态规划 -- 最长公共子序列

最长公共子序列的结构

设序列 X={x1,x2,…,x m} 和 Y={y1,y2,…,y n} 的最长公共子序列为 Z={z1,z2,…,z k}，则有以下结论：

1. 若 x m=y n，则 z k=x m=y n，且 Z k−1（即 Z 去掉最后一个元素 z k 后的子序列）是 X m−1（即 X 去掉最后一个元素 x m 后的子序列）和 Y n−1（即 Y 去掉最后一个元素 y n 后的子序列）的最长公共子序列。

2. 若 x m\=y n 且 z k\=x m，则 Z 是 X m−1 和 Y 的最长公共子序列。

3. 若 x m\=y n 且 z k\=y n，则 Z 是 X 和 Y n−1 的最长公共子序列。

动规方程

c[i] [j]记录序列X和Y的最长公共子序列长度

代码实现

求最长子序列长度

int LCSLength(const char* X, const char* Y, int i, int j) { if (i == 0 || j == 0) { return 0; } else if (X[i] == Y[j]) { return LCSLength(X, Y, i - 1, j - 1) + 1; } else { int t1 = LCSLength(X, Y, i - 1, j);// X int t2 = LCSLength(X, Y, i, j - 1); if (t1 > t2) { return t1; } else { return t2; } } } ​ int main() { const int xm = 7; const int yn = 6; char X[xm + 1] = { '#','A','B','C','B','D','A','B' }; char Y[yn + 1] = { '#','B','D','C','A','B','A' }; ​ int maxlen = LCSLength(X, Y, xm, yn); cout << "maxlen: " << maxlen << endl; ​ return 0; }

求最长子序列（并优化防止重复计算）

int main() { const int xm = 7; const int yn = 6; char X[xm + 1] = { '#','A','B','C','B','D','A','B' }; // 0 1 2 3 4 5 6 7 // X[xm] char Y[yn + 1] = { '#','B','D','C','A','B','A' }; ​ std::vector<std::vector<int> > c(xm + 1, std::vector<int>(yn + 1, 0)); std::vector<std::vector<int> > s(xm + 1, std::vector<int>(yn + 1, 0)); printf("c vec: \n"); Print2Vec(c); printf("s vec: \n"); Print2Vec(s); int maxlen = LCSLength(X, Y, xm, yn,c,s); cout << "maxlen: " << maxlen << endl; cout << "num: " << num << endl; printf("c vec: \n"); Print2Vec(c); printf("s vec: \n"); Print2Vec(s); printf("data: \n"); LCS(X, xm, yn, s); return 0; }

不用递归实现

void Print2Vec(const std::vector<std::vector<int> >& c) { int yn = c[0].size(); int xm = c.size(); printf(" "); for (int i = 0; i < yn; ++i) { printf("%5d", i); } printf("\n"); for (int i = 0; i < xm; ++i) { printf("%3d ", i); for (int j = 0; j < yn; ++j) { printf("%5d", c[i][j]); } printf("\n"); } printf("\n---------------------------\n"); } int NiceLCSLength(const char* X, const char* Y, int xm, int yn, std::vector<std::vector<int> >& c, std::vector<std::vector<int> >& s) { for (int i = 1; i <= xm; ++i) // X { for (int j = 1; j <= yn; ++j) { if (X[i] == Y[j]) { c[i][j] = c[i - 1][j - 1] + 1; s[i][j] = 1; } else { if (c[i - 1][j] > c[i][j - 1]) { c[i][j] = c[i - 1][j]; s[i][j] = 2; } else { c[i][j] = c[i][j - 1]; s[i][j] = 3; } } } Print2Vec(c); } return c[xm][yn]; }