小编Abh*_*hal的帖子

我正在尝试进行动态编程以查找 LCS 的长度。我为此使用了二维数组。但是对于大字符串，它会由于内存溢出而导致运行时错误。请告诉我我应该如何在一维数组中做到这一点以避免内存限制。

#include<bits/stdc++.h>
 #include<string.h> 
 using namespace std;
int max(int a, int b);
int lcs( string X, string Y, int m, int n )
{
   int L[m+1][n+1];
   int i, j;
   for (i=0; i<=m; i++)
   {
     for (j=0; j<=n; j++)
     {
       if (i == 0 || j == 0)
         L[i][j] = 0;

       else if (X[i-1] == Y[j-1])
         L[i][j] = L[i-1][j-1] + 1;

       else
         L[i][j] = max(L[i-1][j], L[i][j-1]);
     }
   }

   return L[m][n];
}

int max(int a, int b)
{
    return (a > …