在这里，我们将看到一种针对 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
以上就是c程序中lcs的空间优化解决方案？的详细内容。