不同路径 II
创始人
2025-01-09 11:00:27
0

以下是一个示例代码,用于解决LeetCode上的“不同路径 II”问题:

def uniquePathsWithObstacles(obstacleGrid):
    # 获取网格的行数和列数
    m = len(obstacleGrid)
    n = len(obstacleGrid[0])
    
    # 创建一个二维数组,用于存储到达每个位置的不同路径数
    dp = [[0] * n for _ in range(m)]
    
    # 初始化起点位置的路径数为1
    dp[0][0] = 1 if obstacleGrid[0][0] == 0 else 0
    
    # 处理第一列的路径数
    for i in range(1, m):
        if obstacleGrid[i][0] == 0:
            dp[i][0] = dp[i-1][0]
    
    # 处理第一行的路径数
    for j in range(1, n):
        if obstacleGrid[0][j] == 0:
            dp[0][j] = dp[0][j-1]
    
    # 计算其他位置的路径数
    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]

在这个解决方法中,我们使用动态规划来计算不同路径的数量。首先,我们创建一个二维数组dp,用于存储到达每个位置的不同路径数。然后,我们初始化起点位置的路径数为1。接下来,我们处理第一列和第一行的路径数,如果网格中的障碍物位置为0,则路径数与上一个位置的路径数相同,否则路径数为0。最后,我们计算其他位置的路径数,对于每个位置,如果网格中的障碍物位置为0,则路径数等于上方和左方位置的路径数之和。最终,返回终点位置的路径数。

这个解决方法的时间复杂度是O(mn),其中m和n分别是网格的行数和列数。空间复杂度也是O(mn),因为我们需要创建一个二维数组来存储路径数。

相关内容

热门资讯

玩家实测!fishpoker透... 玩家实测!fishpoker透视底牌,xpoker透视辅助,分享教程(有挂技巧)1、点击下载安装,微...
揭秘几款!hhpoker有辅助... 1、揭秘几款!hhpoker有辅助吗,wepoker脚本下载,第三方教程(有挂辅助);详细教程。2、...
总算清楚!wepoker祈福有... 总算清楚!wepoker祈福有用吗,wepoker私人局怎么玩,攻略教程(有挂方法);玩家必备必赢加...
记者揭秘!aapoker辅助怎... 记者揭秘!aapoker辅助怎么用,hhpoker是真的还是假的,专业教程(有挂技巧);hhpoke...
盘点一款!epoker透视底牌... 1、盘点一款!epoker透视底牌,大菠萝免费辅助,详细教程(有挂辅助);详细教程。2、大菠萝免费辅...
重大通报!wepoker高级辅... 1、重大通报!wepoker高级辅助,wepoker国外版透视,规律教程(有挂技巧);详细教程。2、...
一秒答解!wepoker究竟有... 一秒答解!wepoker究竟有没有透视,hhpoker脚本下载,介绍教程(有挂透明);建议优先通过w...
每日必备!aapoker公共底... 1、每日必备!aapoker公共底牌,wepoker底牌透视脚本,攻略方法(有挂软件)(UU pok...
今日百科!wepoker破解游... 今日百科!wepoker破解游戏盒子,hardrock透视工具,新2025教程(有挂软件)是由北京得...
1.9分钟了解!wepoker... 自定义wepoker私人局俱乐部辅助系统规律,只需要输入自己想要的开挂功能,一键便可以生成出微扑克专...