最长公共子序列：为什么这是错误的？

int lcs(char * A, char * B)
{
  int m = strlen(A);
  int n = strlen(B);
  int *X = malloc(m * sizeof(int));
  int *Y = malloc(n * sizeof(int));
  int i;
  int j;
  for (i = m; i >= 0; i--)
    {
      for (j = n; j >= 0; j--)
        {
          if (A[i] == '\0' || B[j] == '\0') 
              X[j] = 0;
          else if (A[i] == B[j]) 
              X[j] = 1 + Y[j+1];
          else 
              X[j] = max(Y[j], X[j+1]);
        }
      Y = X;
    }
  return X[0];
}

这可行，但 valgrind 大声抱怨无效读取。我怎么把记忆弄乱了？抱歉，我的 C 内存分配总是失败。

这里的问题是你的桌子的大小。请注意，您将空间分配为

int *X = malloc(m * sizeof(int));
int *Y = malloc(n * sizeof(int));

但是，您使用索引 0 ... m 和 0 ... n，这意味着 X 中需要 m + 1 个槽，Y 中需要 n + 1 个槽。

尝试将其更改为阅读

int *X = malloc((m + 1) * sizeof(int));
int *Y = malloc((n + 1) * sizeof(int));

希望这可以帮助！