题目描述（中等难度）

对62题的变体，增加了一些不能走的格子，用 1 表示。还是输出从左上角到右下角总共有多少种走法。

没做过的话可以先看一下，62 题总结的很详细了，我直接在 62 题的基础上改了。

解法一 递归

时间复杂度：

解法二 动态规划

在62题解法二最后个想法上改。

  2.     int m = obstacleGrid.length;
  3.     int n = obstacleGrid[0].length;
  4.     //起点是障碍，直接返回 0 
  5.     if (obstacleGrid[0][0] == 1)
  6.         return 0;
  7.     int[] dp = new int[n];
  8.     int i = 0;
  9.     //初始化第一行和 62 题不一样了
  10.     for (; i < n; i++) {
  11.         if (obstacleGrid[0][i] == 1) {
  13.             break;
  14.         } else {
  15.             dp[i] = 1;
  16.         }
  17.     }
  18.     //障碍后边的列全部初始化为 0
  19.     for (; i < n; i++) {
  20.         dp[i] = 0;
  21.     }
  22.         //这里改为从 0 列开始了，因为 62 题中从 1 开始是因为第 0 列永远是 1 不需要更新
  24.         for (int j = 0; j < n; j++) {
  25.             if (obstacleGrid[i][j] == 1) {
  26.                 dp[j] = 0;
  27.             } else {
  28.                 //由于从第 0 列开始了，更新公式有 j - 1，所以 j = 0 的时候不更新
  29.                 if (j != 0)
  30.                     dp[j] = dp[j] + dp[j - 1];
  31.             }
  32.         }
  33.     }

时间复杂度：O（m * n）。

空间复杂度：O（n）。

总

添加好友一起进步~

如果觉得有帮助的话，可以点击 给一个 star 哦 ^^