115.不同路径 II
题目
给定一个 m x n 的整数数组 grid。一个机器人初始位于 左上角（即 grid[0][0]）。机器人尝试移动到 右下角（即 grid[m - 1][n - 1]）。机器人每次只能向下或者向右移动一步。
网格中的障碍物和空位置分别用 1 和 0 来表示。机器人的移动路径中不能包含 任何 有障碍物的方格。
返回机器人能够到达右下角的不同路径数量。
测试用例保证答案小于等于 2 * 109。
示例 1：
- 输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
- 输出：2
- 解释：3x3 网格的正中间有一个障碍物。
- 从左上角到右下角一共有 2 条不同的路径： 1. 向右 -> 向右 -> 向下 -> 向下 2. 向下 -> 向下 -> 向右 -> 向右
示例 2：
- 输入：obstacleGrid = [[0,1],[0,0]]
- 输出：1
思路: 动态规划
关键想法
机器人到达某个格子 (i,j) 只能从上方或左方过来。所以到达该格子的路径数 = 到达上方格子的路径数 + 到达左方格子的路径数。
但是，如果当前格子是障碍物，则路径数为 0（不能到达）。
状态定义
设 dp[i][j] 表示从起点到达格子 (i,j) 的不同路径数。
状态转移
如果 obstacleGrid[i][j] == 1（障碍物）：
dp[i][j] = 0
否则：
dp[i][j] = dp[i-1][j] + dp[i][j-1]
边界条件
- 起点 dp[0][0]：如果起点是障碍物，则直接返回 0；否则 dp[0][0] = 1。
- 第一行（i=0）：只能从左方过来，所以 dp[0][j] = dp[0][j-1]（如果当前格子无障碍）；如果遇到障碍物，则该格子及之后所有格子都无法到达（因为只能向右走，一旦堵住后面都过不去），但实际上我们只需在遇到障碍时设为 0，后续格子依赖前一个格子，如果前一个是 0，后面也是 0。
- 第一列（j=0）：同理，只能从上方过来。
class Solution {
fun uniquePathsWithObstacles(obstacleGrid: Array<IntArray>): Int {
val m = obstacleGrid.size
val n = obstacleGrid[0].size
if (obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1] == 1) return 0
val dp = Array(m) { IntArray(n) }
// 初始化起点
dp[0][0] = 1
// 初始化第一列
for (i in 1 until m) {
dp[i][0] = if (obstacleGrid[i][0] == 1) 0 else dp[i-1][0]
}
// 初始化第一行
for (j in 1 until n) {
dp[0][j] = if (obstacleGrid[0][j] == 1) 0 else dp[0][j-1]
}
// 填充其余格子
for (i in 1 until m) {
for (j in 1 until n) {
if (obstacleGrid[i][j] == 1) {
dp[i][j] = 0
} else {
dp[i][j] = dp[i-1][j] + dp[i][j-1]
}
}
}
return dp[m-1][n-1]
}
}
空间优化
因为 dp[i][j] 只依赖上一行和当前行的左邻，所以可以用一维数组 dp 滚动更新。
初始化 dp[0] 为第一行第一列的值，然后逐行更新。
复杂度
- 时间复杂度: O(m × n)每个格子只被访问一次，进行常数次操作。
- 空间复杂度:
- 一维 DP：O(n)（列数）
- 二维 DP：O(m × n)
- 邮箱 ：charon.chui@gmail.com
- Good Luck!