63. 不同路径 II

男娘i 2022-10-10 01:48 176阅读 0赞

> 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
> 
> 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
> 
> 现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
> 
> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNDkwMg_size_16_color_FFFFFF_t_70][]

class Solution {
        public int uniquePathsWithObstacles(int[][] obstacleGrid) {
            /**
            跟上次的不同路径题一样  秒懂稍微多了个条件
                如果当前的是障碍物, 让dp到当前位置的路径为0即可
                    如果第一行有障碍物,障碍物后面的第一行都走不了了
                    如果第一列也是  障碍物后面的第一列都走不了了
             */
             int m=obstacleGrid.length;
             int n=obstacleGrid[0].length;
    
             int [][]dp=new int[m][n];
             for(int i=0;i<m&& obstacleGrid[i][0] == 0;i++){
                     dp[i][0]=1;        
             }
    
        
             for(int i=0;i<n&& obstacleGrid[0][i] == 0;i++){           
                     dp[0][i]=1;
             }
    
             for(int i=1;i<m;i++){
                 for(int j=1;j<n;j++){
                     if(obstacleGrid[i][j]==0){
                           dp[i][j]=dp[i-1][j]+dp[i][j-1];
                     }else{
                         dp[i][j]=0;
                     }
                 }
             }
             return dp[m-1][n-1];
             
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNDkwMg_size_16_color_FFFFFF_t_70]: /images/20221005/0008c68f03be4ab598532b3b7f4f14d3.png

发表评论取消回复

表情：

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

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

相关阅读

相关 LeetCode-63. 不同路径 II

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

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

相关 63. 不同路径 II

63. 不同路径 II 题干描述解题思路 1. 确定dp数组（dp table）以及下标的含义 2. 确定递推公式

淩亂°似流年/ 2023年10月16日 16:03/ 0 赞/ 25 阅读

相关 leetcode63 不同路径II

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

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

相关 63. 不同路径 II

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

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

相关 63. 不同路径 II

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

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

相关 Leetcode 63. 不同路径 II

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

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

相关 leetcode 63 不同路径II

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

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

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

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

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

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

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

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

相关 leetcode:63. 不同路径 II

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

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