力扣:63. 不同路径 II(动态规划)

这篇具有很好参考价值的文章主要介绍了力扣:63. 不同路径 II(动态规划)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目:

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

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

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

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

示例 1:
力扣:63. 不同路径 II(动态规划),算法,python,leetcode,动态规划,算法,python,数据结构

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

  1. 向右 -> 向右 -> 向下 -> 向下
  2. 向下 -> 向下 -> 向右 -> 向右

示例 2:

力扣:63. 不同路径 II(动态规划),算法,python,leetcode,动态规划,算法,python,数据结构

输入:obstacleGrid = [[0,1],[0,0]]
输出:1

提示:

m == obstacleGrid.length
n == obstacleGrid[i].length
1 <= m, n <= 100
obstacleGrid[i][j] 为 0 或 1

思路:

这道题相对于力扣:62. 不同路径(动态规划,附python二维数组的定义)就是有了障碍。
不同路径中我们已经详细分析了没有障碍的情况,有障碍的话,其实就是标记对应的dp数组保持初始值0就可以了。

动规五部曲:

  1. 确定dp数组以及下标的含义(跟上题一样)

这里要明确dp数组的含义,定义dp数组是为了找到不同路径,
dp[i][j] :表示从(0 ,0)出发,到(i, j) 有dp[i][j]条不同的路径。

  1. 确定递推公式

递归公式跟上题一样,dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
但这里需要注意一点,因为有了障碍,(i, j)如果就是障碍的话应该就保持初始状态(初始状态为0)。

代码如下:

                if obstacleGrid[i][j] == 0:
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
  1. dp数组如何初始化

这里的初始化是重点,
如果(i, 0) 这条边有了障碍之后,障碍之后(包括障碍)都是走不到的位置了,所以障碍之后的dp[i][0]应该还是初始值0。下标(0, j)的初始化情况同理。

所以本题初始化代码为:

        for i in range(n):
            if obstacleGrid[0][i] == 0:
                dp[0][i] = 1
            else:
                break
        for j in range(m):
            if obstacleGrid[j][0] == 0:
                dp[j][0] = 1
            else:
                break

注意:一旦遇到obstacleGrid[i][0] == 1的情况,一定要退出循环!不然之后障碍之后的点依旧会被赋值。

  1. 确定遍历顺序(跟上题一样)

从递归公式dp[i][j] = dp[i - 1][j] + dp[i][j - 1] 中可以看出,一定是从左到右一层一层遍历,这样保证推导dp[i][j]的时候,dp[i - 1][j] 和 dp[i][j - 1]一定是有数值。

  1. 举例推导dp数组

拿示例1来举例如题:

力扣:63. 不同路径 II(动态规划),算法,python,leetcode,动态规划,算法,python,数据结构
对应的dp数组如图:
力扣:63. 不同路径 II(动态规划),算法,python,leetcode,动态规划,算法,python,数据结构文章来源地址https://www.toymoban.com/news/detail-800721.html

完整代码:

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        # 获取网格的列数和行数
        n = len(obstacleGrid[0])
        m = len(obstacleGrid)
        
        # 如果起点或终点有障碍物,直接返回0
        if obstacleGrid[0][0] == 1 or obstacleGrid[m - 1][n - 1] == 1:
            return 0
        
        # 初始化一个二维数组dp,用于存储到达每个位置的路径数量
        dp = [[0] * n for _ in range(m)]
        
        # 初始化第一行,如果没有障碍物,则到达每个位置的路径数量为1,否则后面的位置均不可达
        for i in range(n):
            if obstacleGrid[0][i] == 0:
                dp[0][i] = 1
            else:
                break
        
        # 初始化第一列,如果没有障碍物,则到达每个位置的路径数量为1,否则后面的位置均不可达
        for j in range(m):
            if obstacleGrid[j][0] == 0:
                dp[j][0] = 1
            else:
                break
        
        # 计算其余位置的路径数量
        for i in range(1, m):
            for j in range(1, n):
                # 如果当前位置没有障碍物,则到达当前位置的路径数量为到达上方和左方位置的路径数量之和
                if obstacleGrid[i][j] == 0:
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        
        # 返回到达终点的路径数量
        return dp[m - 1][n - 1]

复杂度分析:

  • 时间复杂度:O(n × m),n、m 分别为obstacleGrid 长度和宽度
  • 空间复杂度:O(n × m)

到了这里,关于力扣:63. 不同路径 II(动态规划)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【算法|动态规划No.6】leetcode63. 不同路径Ⅱ

    个人主页:平行线也会相交 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 平行线也会相交 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年02月16日
    浏览(48)
  • 随想录Day39--动态规划: 62.不同路径 , 63. 不同路径 II

    今天的路劲问题,思想和昨天的爬楼梯一样,主要还是找到你这个位置是怎么来的,到达dp[i][j]的方法由到达dp[i - 1][j]的方法再加上到达dp[i][j - 1]的方法和。在初始化时,当i=0或者j=0时,到达他们的只有一条路劲,就是直走,所以对它进行初始化。 63. 不同路径 II 加了一个障

    2024年02月03日
    浏览(59)
  • 力扣算法刷题Day39|动态规划:不同路径 I&II

    力扣题目:#62.不同路径 刷题时长:参考题解后10min 解题方法:动规 复杂度分析 时间O(m*n) 空间O(m*n) 问题总结 初始化二维数组的python语法:i 对应 m,j 对应n 二维遍历顺序,从上到下从左到右通过两层for循环实现,其中startindex应为1 本题收获 动规思路 确定dp数组及下标的含义

    2024年02月12日
    浏览(52)
  • 【算法与数据结构】63、LeetCode不同路径 II

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :参考【算法与数据结构】62、LeetCode不同路径的题目,可以发现本题仅仅是多了障碍物。我们还是用动态规划来做。有障碍物的地方无法到达,因此路径数量为0,只需要将障碍物位

    2024年02月02日
    浏览(57)
  • 算法leetcode|63. 不同路径 II(rust重拳出击)

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

    2024年02月16日
    浏览(49)
  • 我在代码随想录|写代码Day33 | 动态规划| 路径问题| 62.不同路径,63. 不同路径 II,343. 整数拆分

    🔥博客介绍`: 27dCnc 🎥系列专栏: 数据结构与算法 算法入门 C++项目 🎥 当前专栏: 算法入门 专题 : 数据结构帮助小白快速入门算法 👍👍👍👍👍👍👍👍👍👍👍👍 ☆*: .。. o(≧▽≦)o .。.:*☆ ❤️感谢大家点赞👍收藏⭐评论✍️ 今日学习打卡 代码随想录 - 动态规划

    2024年03月11日
    浏览(63)
  • LeetCode刷题笔记【30】:动态规划专题-2(不同路径、不同路径 II)

    参考前文 参考文章: LeetCode刷题笔记【29】:动态规划专题-1(斐波那契数、爬楼梯、使用最小花费爬楼梯) LeetCode链接:https://leetcode.cn/problems/unique-paths/description/ 动态规划 : 创建m×n的数组, 对应这个地图, 数组 val 表示 有几种方法可以走到这一格 最开始, 第一行和第一列v

    2024年02月09日
    浏览(59)
  • 算法Day39 | 62. 不同路径,63. 不同路径 II

    题目链接:62. 不同路径 dp[i][j] 结果为从起点到该点有多少路径。 递归公式: dp[i][j] = dp[i - 1][j] + dp[i][j - 1] 初始化:因为只能从上往下、从左往右走,因此最上侧,最左侧初始化为1(1种路径) 遍历顺序:从上往下,从左往右 也可以使用 滚动 (一维)数组。 其中 dp[j] 表示

    2024年02月10日
    浏览(45)
  • 代码随想录Day33 LeetCode T62不同路径 LeetCode T63 不同路径II

    动规五部曲 1.确定dp数组含义 2.确定递推公式 3.初始化数组 4.确定遍历方式 5.打印dp数组查看分析问题 题目链接:62. 不同路径 - 力扣(LeetCode) 注:n行m列而不是m行n列 1.确定dp数组含义 代表到达此下标有多少条路径 2.确定递推公式 因为只能向右或者向下走,所以到达i,j这个点的

    2024年02月06日
    浏览(50)
  • 算法刷刷刷|动态规划篇|509.斐波那契数| 70.爬楼梯| 746.使用最小花费爬楼梯| 62.不同路径| 63不同路径2| 343.正数拆分 | 96.不同的二叉搜索树

    509. 斐波那契数 斐波那契数 (通常用 F(n) 表示)形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是: F(0) = 0,F(1) = 1 F(n) = F(n - 1) + F(n - 2),其中 n 1 给定 n ,请计算 F(n) 。 70.爬楼梯 746.使用最小花费爬楼梯 给你一个整数

    2023年04月23日
    浏览(56)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包