在这里,我们将看到一种针对 LCS 问题的空间优化方法。 LCS是最长公共子序列。如果两个字符串是“BHHUBC”和“HYUYBZC”,那么子序列的长度是4。动态规划方法已经是它们的一种,但是使用动态规划方法,会占用更多的空间。我们需要 m x n 阶的表,其中 m 是第一个字符串中的字符数,n 是第二个字符串中的字符数。
这里我们将了解如何使用 O(n ) 辅助空间量。如果我们观察旧方法,我们可以在每次迭代中看到,我们需要前一行的数据。并非所有数据都是必需的。所以如果我们做一个大小为2n的表,那就没问题了。让我们看看算法来理解这个想法。
算法
lcs_problem(X, Y) -
'begin
m := length of X
n := length of Y
define table of size L[2, n+1]
index is to point 0th or 1st row of the table L.
for i in range 1 to m, do
index := index AND 1
for j in range 0 to n, do
if i = 0 or j = 0, then
L[index, j] := 0
else if X[i - 1] = Y[j - 1], then
L[index, j] := L[1 – index, j - 1] + 1
else
L[index, j] := max of L[1 – index, j] and L[index, j-1]
end if
done
done
return L[index, n]
end
示例
'#include <iostream>
using namespace std;
int lcsOptimized(string &X, string &Y) {
int m = X.length(), n = Y.length();
int L[2][n + 1];
bool index;
for (int i = 0; i <= m; i++) {
index = i & 1;
for (int j = 0; j <= n; j++) {
if (i == 0 || j == 0)
L[index][j] = 0;
else if (X[i-1] == Y[j-1])
L[index][j] = L[1 - index][j - 1] + 1;
else
L[index][j] = max(L[1 - index][j], L[index][j - 1]);
}
}
return L[index][n];
}
int main() {
string X = "BHHUBC";
string Y = "HYUYBZC";
cout << "Length of LCS is :" << lcsOptimized(X, Y);
}
输出
'Length of LCS is :4