資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究C程式的LCS空間最佳化解決方案是什麼？
這裡我們將看到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
更新於：2019-08-19
155次瀏覽
廣告