首页 > 其他分享 >刷刷刷 Day 39 | 63. 不同路径 II

刷刷刷 Day 39 | 63. 不同路径 II

时间:2023-02-28 21:46:40浏览次数:53  
标签:39 obstacleGrid int 网格 II ++ 63 向下 dp

63. 不同路径 II

LeetCode题目要求

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish”)。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?

网格中的障碍物和空位置分别用 1 和 0 来表示。

示例

图
输入:obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出:2
解释:3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径:
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右
解题思路

上代码

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        // 向右向下,遇到障碍物要避开
        // 有障碍物时,obstacleGrid[i][j] = 1,有一条路,向右或向下时是走不通的
        /**
        --------------------------------------------------------------------
            | 0  1  2
         -----------
         0  | 0  0  0
         1  | 0  1  0
         2  | 0  0  0 

        如上所示的网格,走路径为
        [0,0] -> [0,1] -> [0,2] -> [1,2] -> [2,2] : 右 -> 右 -> 下 -> 下  可达
        [0,0] -> [1,0] -> [2,0] -> [2,1] -> [2,2] : 下 -> 下 -> 右 -> 右  可达
        [0,0] -> [0,1] -> [1,1] = 1 不可达
        [0,0] -> [1,0] -> [1,1] = 1 不可达
        --------------------------------------------------------------------
         */

        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];

        if (obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1] == 1) {
            return 0;
        }

        // 初始化
        for (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;
                System.out.println(dp[i][j]);
            }
        }
        return dp[m-1][n-1];
    }
}

附:学习资料链接

标签:39,obstacleGrid,int,网格,II,++,63,向下,dp
From: https://www.cnblogs.com/blacksonny/p/17166138.html

相关文章

  • ctfshow web入门 命令执行 37-39
    37-39基于GET传参的include()38、39是37的变种分析伪协议常用于文件包含漏洞中文件包含函数有:include、include_once、require、require_once、......
  • 安装guardian报错perl Can't locate getopts.pl in @INC
    在配guardian时遇到的查看源文件发现是这样一句话require'getopts.pl';可是在程序的文件夹下没有这个脚本,并且运行脚本会报错,因为从perl5.16版本开始,这个功能就集成......
  • 1140. 石子游戏 II (Medium)
    问题描述1140.石子游戏II(Medium)爱丽丝和鲍勃继续他们的石子游戏。许多堆石子排成一行,每堆都有正整数颗石子piles[i]。游戏以谁手中的石子最多来决出胜负。爱丽丝......
  • 2363. 合并相似的物品 (Easy)
    问题描述2363.合并相似的物品(Easy)给你两个二维整数数组items1和items2,表示两个物品集合。每个数组items有以下特质:items[i]=[valueᵢ,weightᵢ]其中val......
  • 397. 整数替换 (Medium
    问题描述397.整数替换(Medium)给定一个正整数n,你可以做如下操作:如果n是偶数,则用n/2替换n。如果n是奇数,则可以用n+1或n-1替换n。返回n变为......
  • 1139. 最大的以 1 为边界的正方形 (Medium)
    问题描述1139.最大的以1为边界的正方形(Medium)给你一个由若干0和1组成的二维网格grid,请你找出边界全部由1组成的最大正方形子网格,并返回该子网格中的元素......
  • 【扫描线】LeetCode 253. 会议室 II
    题目链接253.会议室II思路这道题非常类似于坐公交车上下车。样例中intervals=[[0,30],[5,10],[15,20]]可以这么拆解上车:[0,+1],[5,+1],[15,+1]下车:[10,-......
  • Vue项目中通过 avatarUrl: require('@/assets/user-avatar.png')出现required is not
    参考:https://blog.csdn.net/qq_37130872/article/details/128133646useImages.js//获取assets静态图片exportconstgetAssetsImge=(name)=>{returnne......
  • # 代码随想录算法训练营Day28 回溯算法|93.复原IP地址 78.子集 90.子集II
    代码随想录算法训练营93.复原IP地址题目链接:93.复原IP地址给定一个只包含数字的字符串,复原它并返回所有可能的IP地址格式。有效的IP地址正好由四个整数(每个整数位......
  • 剑指 Offer 55 - II. 平衡二叉树(java解题)
    目录1.题目2.解题思路3.数据类型功能函数总结4.java代码1.题目输入一棵二叉树的根节点,判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超......