Penyelesaian yang dioptimumkan ruang untuk LCS dalam program C?

Di sini kita akan melihat kaedah pengoptimuman spatial untuk masalah LCS. LCS ialah urutan biasa terpanjang. Jika dua rentetan ialah "BHHUBC" dan "HYUYBZC", maka panjang urutan ialah 4. Kaedah pengaturcaraan dinamik sudah menjadi salah satu daripadanya, tetapi menggunakan kaedah pengaturcaraan dinamik akan mengambil lebih banyak ruang. Kita memerlukan jadual susunan m x n, dengan m ialah bilangan aksara dalam rentetan pertama dan n ialah bilangan aksara dalam rentetan kedua.

Di sini kita akan melihat cara menggunakan jumlah ruang tambahan O(n). Jika kita melihat pendekatan lama, kita dapat melihat bahawa dalam setiap lelaran, kita memerlukan data dari baris sebelumnya. Tidak semua data diperlukan. Jadi jika kita membuat jadual saiz 2n, itu tidak menjadi masalah. Mari lihat algoritma untuk memahami idea ini.

Algoritma

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

Contoh

#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

#🎜#rrreee#🎜 🎜🎜#

Atas ialah kandungan terperinci Penyelesaian yang dioptimumkan ruang untuk LCS dalam program C?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!