不同路径 II
- https://leetcode.cn/problems/unique-paths-ii/
描述
-
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。 -
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
-
网格中的障碍物和空位置分别用 1 和 0 来表示。
示例1
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右
示例2
输入：obstacleGrid = [[0,1],[0,0]]
输出：1
提示
- m == obstacleGrid.length
- n == obstacleGrid[i].length
- 1 <= m, n <= 100
- obstacleGrid[i][j] 为 0 或 1
算法实现
1 ）方案 1
function uniquePathsWithObstacles(obstacleGrid: number[][]): number {// 1. 获取当前矩阵的行和列const m = obstacleGrid.length // 行const n = obstacleGrid[0].length // 列// 2. 准备好最终的数据结构：初始化一个m x n的矩阵, 使用矩阵来计算const matrix: number[][] = new Array(m).fill(0).map(_ => new Array(n).fill(0));// 3. 遍历第一列，根据给定矩阵，初始化结果矩阵中第一列的值for (let i = 0; i < m && obstacleGrid[i][0] === 0; i++) {matrix[i][0] = 1}// 4. 遍历第一行，根据给定矩阵，初始化结果矩阵中第一行的值for (let i = 0; i < n && obstacleGrid[0][i] === 0; i++) {matrix[0][i] = 1}// 遍历原始矩阵这个二维数组，因为第一列和第一行已经遍历过了for (let i = 1; i < m; i++) {for (let j = 1; j < n; j++) {// 中间有障碍物，直接跳出当前if (obstacleGrid[i][j] === 1) continue// 分解后的问题求解公式，matrix[i][j] = matrix[i - 1][j] + matrix[i][j - 1]}}// 最后一步存储的值return matrix[m - 1][n - 1]
}
- 这个是官方示例，逆向思维，原矩阵中1是障碍物，0是可移动的位置
- 为了方便计算, 我们通过一个新的矩阵来累加计算，反过来，可移动的为1，障碍物为0
- 因为可移动的位置参与计算，障碍物不参与计算
- 核心公式是：F(m*n) = F((m-1) * n) + F(m * (n - 1))
- 动态规划就是从基础开始计算，直到逐步接近我们最终的目标，也就是最后的一个位置 matrix[m - 1][n - 1]
- 我一开始没想到怎么做，看了官方示例，瞬间就明白了
