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

问题描述

求两字符序列的最长公共字符子序列。

补充说明&＃xff1a;

• 不强制要求子串的字符连续出现在原始的2个字符序列中。
• 测试字符序列&＃xff0c;比如&＃xff0c;

解决思路

确立状态方程

参考图1.表格所示&＃xff0c;记 LCS(x, y) 为表格中的元素&＃xff0c;该元素表示截止到第1序列中的字符‘x’和第2序列中的字符‘y’时已有多少个相同的字符个数&＃xff0c;即公共子序列的长度。

图1.

图1.中箭头的方向表示当前的“公共子序列长度”继承自哪个前一个位置&＃xff0c;这里&＃xff0c;如果有

代码

///////////////////////////////////////////////////////////////
//
// &＃64;2017-10-13 DP : LCS 最长公共子序列
// 时间复杂度 O(n*m)
// 空间复杂度 O(n*m)
//
///////////////////////////////////////////////////////////////
// 头文件
#include
#include using namespace std;//&＃64;2017-10-13 TY 需考虑使用变长度数组 , 考虑使用 vector 实现变长二维数组
#define ArraySize 16
int dp[ArraySize][ArraySize]&＃61;{0};///////////////////////////////////////////////////////////////
// DP LCS API
void DpLCS(vector<char>::iterator pVecX, vector<char>::iterator pVecY, int x, int y);///////////////////////////////////////////////////////////////
//
int main(void)
{char cBufX[] &＃61; {&＃39;A&＃39;, &＃39;B&＃39;, &＃39;C&＃39;, &＃39;B&＃39;, &＃39;D&＃39;, &＃39;A&＃39;, &＃39;B&＃39;};char cBufY[] &＃61; {&＃39;B&＃39;, &＃39;D&＃39;, &＃39;C&＃39;, &＃39;A&＃39;, &＃39;B&＃39;, &＃39;A&＃39;};vector<char> vecX, vecY;// 赋初值for (int i&＃61;0; i<(sizeof(cBufX)/sizeof(char)); i&＃43;&＃43;){vecX.push_back(cBufX[i]);//cout <}for (int i&＃61;0; i<(sizeof(cBufY)/sizeof(char)); i&＃43;&＃43;){vecY.push_back(cBufY[i]);//cout <} // DP : LCS // 二维数组存储的是 状态方程 的值 for (int i&＃61;0; ifor (int j&＃61;0; jif (vecX.at(i) &＃61;&＃61; vecY.at(j)){dp[i&＃43;1][j&＃43;1] &＃61; dp[i][j]&＃43;1;}else{dp[i&＃43;1][j&＃43;1] &＃61; std::max(dp[i][j&＃43;1], dp[i&＃43;1][j]);}}}/*// 打印 表格 content for (int i&＃61;0; i // Graph DpLCS(vecX.begin(), vecY.begin(), vecX.size(), vecY.size());system("pause");return 0;
}///////////////////////////////////////////////////////////////
// &＃64;2017-10-13 DP LCS
// DP : LCS
// (1) 从数列结尾向前递归.
// (2) 结束的边界条件是 return ;
void DpLCS(vector<char>::iterator pVecX, vector<char>::iterator pVecY, int x, int y)
{if (x &＃61;&＃61; 0 || y &＃61;&＃61; 0)return ;if (*(pVecX&＃43;x-1) &＃61;&＃61; *(pVecY&＃43;y-1)){DpLCS(pVecX, pVecY, x-1, y-1);cout <<*(pVecX&＃43;x-1) <<&＃39; &＃39;;}else if (dp[x-1][y] &＃61;&＃61; dp[x][y]){DpLCS(pVecX, pVecY, x-1, y);}else{DpLCS(pVecX, pVecY, x, y-1);}
}