c++ - 陷入二维逻辑

Question

您好，我已经为最不常见的子序列问题编写了一个程序，

并坚持 2-dim 数组传递和遍历。请提供帮助。

下面是一段代码。

void backtrack(char x[], char y[], int L[][7], int m, int n)
{
  if(m == 0 || n == 0)
    return;

  else if(x[m-1] == y[n-1])
  {
    backtrack(x, y, L, m-1, n-1);
    cout << x[m-1] << " ";
  }

  else
  {
    if(L[m-1][n] > L[m][n-1])
      backtrack(x, y, L, m-1, n);
    else
      backtrack(x, y, L, m, n-1);
  }
}


int lcs_length(char x[], char y[], const int m, const int n)
{
  int L[m+1][n+1];

  for(int i=0; i<=m; i++)
  {     
    for(int 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]); 
    }           
  }     
  backtrack(x, y, L, m+1, n+1);
  return L[m][n];
}



int main(int argc, char *argv[])
{
  char x[] =  "ABCDGH";
  char y[] =  "AEDFHR";

  int m = sizeof x / sizeof *x;
  int n = sizeof y / sizeof *y;

  cout << lcs_length(x, y, m, n);

  return EXIT_SUCCESS;
}

我基本上停留在从 lcs_length() 调用回溯函数，因为我无法在回溯中传递/遍历 2-dim 数组...

请帮助..

谢谢。

Answer 1

你的 lcs_length 中的二维数组 L 不是真正的 c 数组，因为你使用变量来设置元素的数量。设置其大小时，例如到 int L[100][7] 一切正常。

但为了解决您的问题，我宁愿使用真正的动态数组，例如:

int **L = new int* [m+1];
for (int i = 0; i < m+1; i++)
   L[i] = new int[n+1];

然后您可以将数组作为 int ** L 传递。