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

最长公共子序列的结构设序列 X{x1,x2,…,x m} 和 Y{y1,y2,…,y n} 的最长公共子序列为 Z{z1,z2,…,z k}则有以下结论若 x my n则 z kx my n且 Z k−1即 Z 去掉最后一个元素 z k 后的子序列是 X m−1即 X 去掉最后一个元素 x m 后的子序列和 Y n−1即 Y 去掉最后一个元素 y n 后的子序列的最长公共子序列。若 x m\y n 且 z k\x m则 Z 是 X m−1 和 Y 的最长公共子序列。若 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::vectorstd::vectorint c(xm 1, std::vectorint(yn 1, 0)); std::vectorstd::vectorint s(xm 1, std::vectorint(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::vectorstd::vectorint 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::vectorstd::vectorint c, std::vectorstd::vectorint 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]; }