计算 LCS 的长度
-
// 为了实现方便，从数组的第 1 格开始存入序列。
-
int s1[7+1] = {0, 2, 5, 7, 9, 3, 1, 2};
-
int s2[5+1] = {0, 3, 5, 3, 2, 8};
-
// DP 的表格
-
int array[7+1][5+1];
-
void LCS()
-
{
-
将 array\[x\]\[0\] 和 array\[0\]\[x\] 都设为 0 ; -
for (int i = 1; i <= s1\_length; i++) -
for (int j = 1; j <= s2\_length; j++) -
if (s1\[i\] == s2\[j\]) -
// 这里加上的 1 是指 e1 的长度为 1 -
array\[i\]\[j\] = array\[i-1\]\[j-1\] + 1; -
else -
array\[i\]\[j\] = max(array\[i-1\]\[j\], array\[i\]\[j-1\]); -
cout << "LCS 的长度是" << array\[seq1\_length\]\[seq2\_length\]; -
}
找出一个 LCS
-
// 为了实现方便，从数组的第 1 格开始存入序列。
-
int s1[7+1] = {0, 2, 5, 7, 9, 3, 1, 2};
-
int s2[5+1] = {0, 3, 5, 3, 2, 8};
-
// DP 的表格
-
int array[7+1][5+1];
-
// 记录这一格的最大值是从哪一格求得的
-
int prev[7+1][5+1];
-
void LCS()
-
{
-
将 array\[x\]\[0\] 和 array\[0\]\[x\] 都设为 0 ; -
for (int i = 1; i <= s1\_length; i++) -
for (int j = 1; j <= s2\_length; j++) -
if (s1\[i\] == s2\[j\]) -
{ -
// 这里加上的 1 是指 e1 的长度为 1 -
array\[i\]\[j\] = array\[i-1\]\[j-1\] + 1; -
prev\[i\]\[j\] = 左上方; -
} -
else -
{ -
if (array\[i-1\]\[j\] < array\[i\]\[j-1\]) -
{ -
array\[i\]\[j\] = array\[i\]\[j-1\]; -
prev\[i\]\[j\] = 左方; -
} -
else -
{ -
array\[i\]\[j\] = array\[i-1\]\[j\]; -
prev\[i\]\[j\] = 上方; -
} -
} -
cout << "LCS 的长度是" << array\[s1\_length\]\[s2\_length\]; -
cout << "LCS 为 "; -
print\_LCS(s1\_length, s2\_length); -
}
-
void print_LCS(int i, int j)
-
{
-
// 第一个或第二个 sequence 为空的的时候就可停止了 -
if (i==0 || j==0) return; -
if (prev\[i\]\[j\] == 左上方) -
{ -
print\_LCS(i-1, j-1); -
cout << s1\[i\]; // 印出 LCS 的元素 -
}
-
else if (prev [i][j] == 上方)
-
print\_LCS(i-1, j); -
else if (prev [i][j] == 左方)
-
print\_LCS(i, j-1); -
}