【算法|动态规划No.6】leetcode63. 不同路径Ⅱ

**不同路径Ⅱ**

**题目描述**

有一个 `m x n` 的网格，其中一些单元格是障碍物，而另一些单元格是可以通过的。给定两个整数 `m` 和 `n`, 返回从左上角 (0,0) 到右下角 `(m-1, n-1)` 的路径数量。

**注意**

当一个障碍物和一个可行单元格相遇时，障碍物会覆盖可行单元格。请假设从左上角到右下角的路径总数为 `k`。

**示例1**

输入：`obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]`, `m =3`, `n =3`
输出：`2`

**示例2**

输入：`obstacleGrid = [[0,1,0],[0,1,0],[0,0,0]]`, `m =3`, `n =4`
输出：`1`

**示例3**

输入：`obstacleGrid = [[0,0,0,0],[0,1,2,0],[0,3,0,0]]`, `m =4`, `n =4`
输出：`7`

**动态规划解决方案**

我们可以使用动态规划来解决这个问题。假设 `dp[i][j]` 表示从左上角 `(0,0)` 到右下角 `(i-1, j-1)` 的路径数量。

**状态转移方程**

对于每个单元格 `(i, j)`,我们有以下几种情况：

* 如果该单元格是障碍物，则 `dp[i][j] =0`。
* 如果该单元格是可行的，则 `dp[i][j] = dp[i-1][j] + dp[i][j-1]`。

**初始条件**

我们有以下初始条件：

* `dp[0][0] =1`, 因为从左上角 `(0,0)` 到右下角 `(0-1,0-1)` 的路径数量为1。
* `dp[i][0] =0` 和 `dp[0][j] =0`, 因为从左上角 `(i,0)` 或 `(0, j)` 到右下角 `(i-1, n-1)` 或 `(m-1, j-1)` 的路径数量均为0。

**代码实现**

def uniquePathsWithObstacles(obstacleGrid):
 m = len(obstacleGrid)
 n = len(obstacleGrid[0])
 # 初始化 dp 数组 dp = [[0 for _ in range(n)] for _ in range(m)]
 # 设置初始条件 dp[0][0] =1 - obstacleGrid[0][0]
 for i in range(1, m):
 dp[i][0] = int(dp[i-1][0] !=0)
 for j in range(1, n):
 dp[0][j] = int(dp[0][j-1] !=0)
 # 计算状态转移方程 for i in range(1, m):
 for j in range(1, n):
 if obstacleGrid[i][j] ==0:
 dp[i][j] = dp[i-1][j] + dp[i][j-1]
 # 返回结果 return dp[m-1][n-1]

# 测试用例obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
m =3n =3print(uniquePathsWithObstacles(obstacleGrid)) # 输出:2obstacleGrid = [[0,1,0],[0,1,0],[0,0,0]]
m =3n =4print(uniquePathsWithObstacles(obstacleGrid)) # 输出:1obstacleGrid = [[0,0,0,0],[0,1,2,0],[0,3,0,0]]
m =4n =4print(uniquePathsWithObstacles(obstacleGrid)) # 输出:7