宁波建站模板源码,wordpress空俩格,网站做贷款许可证,上海网站建设公司推荐排名【力扣】63. 不同路径 II
一个机器人位于一个 m m m x n n n 网格的左上角 #xff08;起始点在下图中标记为 “Start” #xff09;。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角#xff08;在下图中标记为 “Finish”#xff09;。 现在考虑网格…【力扣】63. 不同路径 II
一个机器人位于一个 m m m x n n n 网格的左上角 起始点在下图中标记为 “Start” 。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角在下图中标记为 “Finish”。 现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径网格中的障碍物和空位置分别用 1 和 0 来表示。
示例 1
起点000障碍000终点
输入obstacleGrid [[0,0,0],[0,1,0],[0,0,0]] 输出2 解释3x3 网格的正中间有一个障碍物。 从左上角到右下角一共有 2 条不同的路径 向右 - 向右 - 向下 - 向下 向下 - 向下 - 向右 - 向右
示例 2
起点障碍0终点
输入obstacleGrid [[0,1],[0,0]] 输出1
提示 m obstacleGrid.length n obstacleGrid[i].length 1 m, n 100 obstacleGrid[i][j] 为 0 或 1
题解
确定 dp 数组以及下标的含义 dp[i][j] 表示从 (0,0) 出发到 (i, j) 有 dp[i][j] 条不同的路径。确定递推公式 想要求 dp[i][j]只能有两个方向来推导出来即 dp[i - 1][j] 和 dp[i][j - 1]。 dp[i - 1][j] 表示是从 (0, 0) 的位置到 (i - 1, j) 有几条路径dp[i][j - 1]同理 dp[i][j] dp[i - 1][j] dp[i][j - 1]因为 dp[i][j] 只有这两个方向过来。 因为有了障碍(i, j) 如果就是障碍的话应该就保持初始状态初始状态为0。dp 数组如何初始化 dp[i][0] 一定都是1因为从 (0, 0) 的位置到 (i, 0) 的路径只有一条那么 dp[0][j] 也同理。 但如果 (i, 0) 这条边有了障碍之后障碍之后包括障碍都是走不到的位置了所以障碍之后的 dp[i][0] 应该还是初始值0。下标(0, j)的初始化情况同理。确定遍历顺序 dp[i][j] 都是从其上方和左方推导而来举例推导 dp 数组打印 dp 数组
public class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {int m obstacleGrid.length;int n obstacleGrid[0].length;int[][] dp new int[m][n];//如果在起点或终点出现了障碍直接返回0if (obstacleGrid[m - 1][n - 1] 1 || obstacleGrid[0][0] 1) {return 0;}//dp数组初始化若有障碍后面都是0for (int i 0; i m obstacleGrid[i][0] 0; i) {dp[i][0] 1;}for (int j 0; j n obstacleGrid[0][j] 0; j) {dp[0][j] 1;}//遍历顺序for (int i 1; i m; i) {for (int j 1; j n; j) {dp[i][j] (obstacleGrid[i][j] 0) ? dp[i - 1][j] dp[i][j - 1] : 0;}}return dp[m - 1][n - 1];}
}
