相似题目：
【LeetCode】62. 不同路径（动态规划）

一、题目描述

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

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

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

网格中的障碍物和空位置分别用 1 和 0 来表示。
说明：m 和 n 的值均不超过 100。
示例 1:

输入:
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
输出: 2
解释:
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

二、解题思路 & 代码

  1. 如果网格 ( i , j ) (i,j) (i,j) 上有障碍物，则 d p [ i ] [ j ] dp[i][j] dp[i][j] 值为 0 0 0，表示走到该格子的方法数为 0 0 0；
  2. 否则网格 ( i , j ) (i,j) (i,j) 可以从网格 ( i − 1 , j ) (i−1,j) (i−1,j) 或者 网格 ( i , j − 1 ) (i,j−1) (i,j−1) 走过来，因此走到该格子的方法数为走到网格 ( i − 1 , j ) (i−1,j) (i−1,j) 和网格 ( i , j − 1 ) (i,j−1) (i,j−1) 的方法数之和，即
    d p [ i , j ] = d p [ i − 1 , j ] + d p [ i , j − 1 ] dp[i,j]=dp[i−1,j]+dp[i,j−1] dp[i,j]=dp[i−1,j]+dp[i,j−1]

状态转移方程如下：
d p [ i ] [ j ] = { d p [ i − 1 , j ] + d p [ i , j − 1 ] , 如果(i, j)上无障碍物 0 , 如果(i, j)上有障碍物 dp[i][j]= \begin{cases} dp[i−1,j]+dp[i,j−1], & \text {如果(i, j)上无障碍物} \\ 0, & \text{如果(i, j)上有障碍物} \end{cases} dp[i][j]={ dp[i−1,j]+dp[i,j−1],0,​如果(i, j)上无障碍物如果(i, j)上有障碍物​

2.1 二维 dp

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m = len(obstacleGrid)
        n = len(obstacleGrid[0])
        dp = [[0] * n for i in range(m)]    # 不能初始化为全 1 ，因为有可能左边和上面都是 0，怎么相加也不会得到 1
        for i in range(m):
            for j in range(n):
                if obstacleGrid[i][j] == 1:  # 有障碍物
                    dp[i][j] = 0
                else:                        # 无障碍物
                    if i == 0 and j == 0:    # 起始位置
                        dp[i][j] = 1
                    else:dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[-1][-1]

2.2 一维 dp

给左面和上面各加一个障碍边

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m = len(obstacleGrid)
        n = len(obstacleGrid[0])
        dp = [1] + [0] * n  
        for i in range(m):
            for j in range(n):
                if obstacleGrid[i][j]:
                    dp[j] = 0
                else:
                    dp[j] = dp[j] + dp[j-1]
        return dp[-2]