leetcode:63. 不同路径 II

浅浅的花香味﹌ 2022-04-05 16:50 196阅读 0赞

## 题目: ##

一个机器人位于一个 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.  向下 -> 向下 -> 向右 -> 向右

## 分析: ##

dp,同上

## 代码: ##

public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    		if (obstacleGrid == null || obstacleGrid.length == 0 || obstacleGrid[0].length == 0) {
    			return 0;
    		}
    		int m = obstacleGrid.length;
    		int n = obstacleGrid[0].length;
    
    		int[][] dp = new int[m][n];
    
    		for (int i = 0; i < m; i++) {
    			for (int j = 0; j < n; j++) {
    				if (obstacleGrid[i][j] == 1)
    					continue;
    				if (i == 0 && j == 0)
    					dp[0][0] = 1;
    				if (i > 0)
    					dp[i][j] += dp[i - 1][j];
    				if (j > 0)
    					dp[i][j] += dp[i][j - 1];
    			}
    		}
    
    		return dp[m - 1][n - 1];
    	}

## 效率: ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0NTE2NTQ5_size_16_color_FFFFFF_t_70]

## 总结: ##

dp

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0NTE2NTQ5_size_16_color_FFFFFF_t_70]: /images/20220405/fa1a3424f4524bf89367cbb987601df5.png

发表评论取消回复

表情：

评论列表（有 0 条评论，196人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode-63. 不同路径 II

题目来源 [63. 不同路径 II][63. _ II] 递归 class Solution { public int u

缺乏、安全感/ 2024年03月26日 17:28/ 0 赞/ 77 阅读

相关 leetcode63 不同路径II

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为“Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Fi

阳光穿透心脏的1/2处/ 2023年06月19日 04:20/ 0 赞/ 136 阅读

相关 leetcode63 不同路径II

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为“Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Fi

冷不防/ 2023年06月16日 10:43/ 0 赞/ 19 阅读

相关 63. 不同路径 II

\\\ 解题思路在62题的基础上加上了判断每一个格子能不能走还是62题的做法,把不能走的格子置为0即可 \\\ 代码 class Solution {

Myth丶恋晨/ 2022年10月29日 07:49/ 0 赞/ 188 阅读

相关 63. 不同路径 II

> 一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为“Start” ）。 > > 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中

男娘i/ 2022年10月10日 01:48/ 0 赞/ 194 阅读

相关 Leetcode 63. 不同路径 II

题目重述一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为“Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下

比眉伴天荒/ 2022年09月03日 13:14/ 0 赞/ 190 阅读

相关 leetcode 63 不同路径II

前言题目：[63. 不同路径 II][63. _ II] 参考题解：[不同路径 II-代码随想录][II-] -------------------- 提交代码

川长思鸟来/ 2022年08月28日 05:46/ 0 赞/ 189 阅读

相关 LeetCode 63.Unique Paths II (不同路径 II)

题目描述：一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为“Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（

比眉伴天荒/ 2022年05月10日 05:36/ 0 赞/ 212 阅读

相关 LeetCode-63 不同路径 II（dp）

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为“Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Fi

Love The Way You Lie/ 2022年04月24日 02:38/ 0 赞/ 260 阅读

相关 leetcode:63. 不同路径 II

题目: 一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为“Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图

浅浅的花香味﹌/ 2022年04月05日 16:50/ 0 赞/ 197 阅读