63.unique-paths-ii.md

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

线性 DP

递推

状态

$f[i][j]$表示到达$(i，j)$ 的方案数

转换方程

如果当前位置为障碍物，即$grid[i-1][j-1] == 1$, 则有 $f[i][j] = 0$ 如果当前位置可走，即$grid[i-1][j-1] == 0$, 则有 $f[i][j] = f[i-1][j] + f[i][j-1]$

边界

为方便计算，特殊处理，二维矩阵上边和左边分别加上 障碍物，充当边界

• $i==0, j==0$，表示边界，$f[0...m] = 0, f[0...n] = 0$
• $dp[1][1] = 1$，表示起始位置

代码实现

class Solution {
    public int uniquePathsWithObstacles(int[][] g) {
        int m = g.length, n = g[0].length;
        int[][] f = new int[m+1][n+1];
        if (g[0][0] == 1) return 0;
        f[1][1] = 1;
        for (int i = 1; i<= m; i++){
            for (int j = 1; j<= n; j++){
                if (i == 1 && j== 1) continue;
                if (g[i-1][j-1] == 1) {
                    f[i][j] = 0;
                    continue;
                }
                f[i][j] = f[i-1][j] + f[i][j-1];
            }
        }
        return f[m][n];
    }
}

var uniquePathsWithObstacles = function (grid) {
  let m = grid.length,
    n = grid[0].length;
  let dp = [];
  for (let i = 0; i <= m; i++) dp[i] = new Array(n + 1).fill(0);
  if (grid[0][0] == 1) return 0;
  dp[1][1] = 1;
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (i == 1 && j == 1) continue;
      if (grid[i - 1][j - 1] == 1) dp[i][j] = 0;
      else dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    }
  }
  return dp[m][n];
};

---

同类型题目

• 62.不同路径.md

• 63.不同路径 II.md

• 64.最小路径和.md

• 72.编辑距离.md