P77. 路径数量(含障碍物)

https://algocasts.io/episodes/qjG08bGK

您好,4:33秒前后,定义一维数组的时候,您说用行数和列数中的较小值来定义一维数组以节省空间,这里好像错了?应该是用列数来定义吧。如果是用较小值来定义,那么比如 [[0, 0]] 这样一个一行两列的数组, 一维数组的大小就是1,在执行 d[j] = grid[i][j] == 1 ? 0 : d[j] + d[j-1]; 的时候,j - 1 就越界了

@yqysummy

没有错的。用较小值来定义辅助一维数组的话,下面的处理代码就要做相应的修改。因为这涉及到我们是一行行按行进行处理,还是一列列按列进行处理

直接用列数或行数来定义辅助数组比较简单,因为这样的话就很明确,到底我们是按行还是按列进行处理。但如果想要根据数组大小,动态地决定按行处理还是按列处理,以此来最小化辅助数组 d 的空间,那相应的代码里也需要一个变量 byRow 动态地判断具体的一次处理是按行还是按列进行的。

以下是参考代码:

  public int uniquePathsWithObstacles(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    boolean byRow = n < m;    // 是否按行进行处理;false 的话则按列进行处理。
    int min = Math.min(m, n);
    int max = Math.max(m, n);
    int[] d = new int[min];  // 用较小的维度值来开辅助空间
    d[0] = grid[0][0] == 1 ? 0 : 1;

    for (int i = 0; i < max; ++i) {
      int first = byRow ? grid[i][0] : grid[0][i];
      d[0] = first == 1 ? 0 : d[0];
      for (int j = 1; j < min; ++j) {
        int cur = byRow ? grid[i][j] : grid[j][i];
        d[j] = cur == 1 ? 0 : d[j] + d[j-1];
      }
    }
    return d[min-1];
  }

最后说一句,一般情况下我们都不会去做以上的优化,因为这种优化带来的改进是在同一数量级的,却使得代码变得更复杂。因此你会看到所有将二维辅助空间优化到一维的情况,我一般都直接使用列数 n 来开辅助空间。

1赞

明白了,感谢解惑!