在网格上查找唯一路径的数量

Question

我正在尝试了解如何使用动态编程解决在网格中查找所有唯一路径的问题：

机器人位于m x n网格的左上角（下图中标记为“开始”）。机器人只能在任何时间点向下或向右移动。机器人正试图到达网格的右下角（下图中标记为“Finish”）。有多少种可能的独特路径？

我正在看这篇文章，我想知道为什么在下面的解决方案中，矩阵被初始化为M_MAX 2和N_MAX 2，以及为什么在backtrack的函数签名中，最后一个参数被初始化为int mat[[N_MAX 2]

const int M_MAX = 100;
const int N_MAX = 100;

int backtrack(int r, int c, int m, int n, int mat[][N_MAX+2]) {
  if (r == m && c == n)
    return 1;
  if (r > m || c > n)
    return 0;

  if (mat[r+1][c] == -1)
    mat[r+1][c] = backtrack(r+1, c, m, n, mat);
  if (mat[r][c+1] == -1)
    mat[r][c+1] = backtrack(r, c+1, m, n, mat);

  return mat[r+1][c] + mat[r][c+1];
}

int bt(int m, int n) {
  int mat[M_MAX+2][N_MAX+2];
  for (int i = 0; i < M_MAX+2; i++) {
    for (int j = 0; j < N_MAX+2; j++) {
      mat[i][j] = -1;
    }
  }
  return backtrack(1, 1, m, n, mat);
}

然后在作者自下而上的解决方案中：

const int M_MAX = 100;
const int N_MAX = 100;

int dp(int m, int n) {
  int mat[M_MAX+2][N_MAX+2] = {0};
  mat[m][n+1] = 1;

  for (int r = m; r >= 1; r--)
    for (int c = n; c >= 1; c--)
      mat[r][c] = mat[r+1][c] + mat[r][c+1];

  return mat[1][1];
}

我不知道这行的目的是什么mat[m][n1]=1 发球。

我不熟悉Java，所以如果这些问题归结为语法或语言特定的问题，我深表歉意。




Answer 1

首先，请注意，作者和第二个解决方案都使用基于1的索引。因此，当然，mat[M_MAX1][N_MAX1]是非常合理的。

现在，请注意作者使用的逻辑。

mat[r][c] = mat[r+1][c] + mat[r][c+1];

因此，为了防止r1或c1在c=n1或r=m1时越界，而不是添加这样的if语句：

if (r == m)
    mat[r][c] = mat[r][c+1];
if (c == n)
    mat[r][c] = mat[r+1][c];

他决定简单地添加一个额外的行或列，其中存储0值。因此：

mat[M_MAX+2][N_MAX+2] = {0};

最后，在自下而上的方法中，必须将mat[m][n]初始化为1。与其这样做，不如知道mat[m][n]=mat[m1][n]mat[m][n1] ，他初始化：

mat[m][n+1] = 1; // mat[m+1][n] = 0;

欢迎在评论中提出任何问题。