欢迎访问欧博亚洲(Allbet Game)!

首页科技正文

绥化物流:动态计划两题连刷,移动下标的小技巧

admin2020-05-196

本文始发于小我私家民众号:TechFlow,原创不易,求个关注


今天是LeetCode的37篇,我们继续愉快的刷题。今天要刷的问题输出LeetCode 63和64两题,分别是Unique Paths II和Minimum Path Sum。

从问题的名称我们就可以看出来,今天的问题都和path有关,实在不止云云,这两题的题意也险些一样,本质上都是上一篇文章所讲的LeetCode 62题的延伸和拓展。这也是我们把这两题放在一起解决的缘故原由。

Unique Paths II

我们先来看第一题,Unique Paths II。它和62题基本一样,都是机器人走一个矩形迷宫求解路径总数的问题。也许就像是下面这张图一样,机器人从左上角出发,往右下角前进。

img

机器人只能往下或者是往右移动,不能往左或者是往上。而且这一次给定的矩形迷宫不再是所有点都可以接见了,有些点设置了路障。机器人不能接见设置了路障的点,叨教在此情形下,机器人从起点走到终点的路径一共有若干条?

样例

Input:
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
Output: 2
Explanation:
There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

从样例可以看出来,问题用一个二维数组代表了矩形,数组当中为1的点示意了路障。

若是你读过我们上一篇文章,做过LeetCode 62题,你会发现这题险些是完全一样的翻版,而且连解题思绪都一样。若是你没有做过,可以通过下面的传送门回首一下:

LeetCode 62: 想到动态计划就无敌了?这道题另有更牛的解法

我们套用一下62题的思绪,其中动态计划的解法是完全适用的。路障的存在只会影响路障的点自己以及它四周可以转移到的点,对于它自己而言,它无法到达,自然可接见的路径数就是0。而对于它转移到的点来说,这点无法接见,自然孝敬也是0。以是我们只需要在转移的历程当中将路障的位置置为0即可。

而通过排列组合求解谜底的方式就无法使用了,由于路障和路障之间会有影响,以是我们没有办法仅仅通过排列组合就求出起点到路障处的路径数目,也无法确定这个路障对于总体路径数目带来的转变量,更无法确定路障是否有把所有通路堵死。这些点之间相互影响,仅仅通过数学很难盘算,以是不太方便使用。

以是我们只能通过动态计划来求解,这段代码和上一题的险些也一样,只不外做了一点细微的改动,加上了路障的判断。

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        n, m = len(obstacleGrid), len(obstacleGrid[0])
        # 我们维护的下标i从1到n,j从1到m
        dp = [[0 for _ in range(m+2)] for _ in range(n+2)]
        
        dp[0][1] = 1
        for i in range(1, n+1):
            for j in range(1, m+1):
               # 判断当前位置是否可达,由于下标局限不一致,以是要-1
                if obstacleGrid[i-1][j-1] == 1:
                    dp[i][j] = 0
                else:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[n][m]

这题看着简朴,代码想要一次性写对不容易,有一个坑点是我们dp数组维护的下标局限和问题给定的路障数组的下标是不一样的,我们设置了下标从1最先,这样可以不用思量转移时数组越界的问题。既然下标设置从1最先,我们在判断对应位置是否是路障的时刻,就需要i和j都-1。

我们继续看下一题。

Minimum Path Sum

题意同样是机器人走矩形迷宫,不外稍有差别的是,这一题当中加上了路径长度的判断,我们从起点最先,每到一个点都市有一个消耗。现在我们想要让机器人从起点到达终点,所需要的最小消耗。

样例

Input:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.

若是你理解了上面一题的思绪来做这题,险些是秒杀的,由于解题的思绪完全一样,只不外是我们dp数组当中维护不再是到每个点的路径数目,而是起点最先到这个点最小的距离。

对于每一个点i,j来说,它有两个泉源,分别是i-1,j 和i, j-1。状态转移方程就是。这里的cost数组也就是问题给的每个点的破费。

我们直接来看代码:

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        n = len(grid)
        if n == 0:
            return 0
        m = len(grid[0])
        
        # 同样,我们dp维护的下标从1最先,初始化时赋值成无穷大
        dp = [[0x3f3f3f3f for _ in range(m+2)] for _ in range(n+2)]
        
        # 将0,1位置赋值成0,给(1, 1)提供一个消耗为0的入口
        dp[0][1] = 0
        
        for i in range(1, n+1):
            for j in range(1, m+1):
               # 由于下标从1最先,不用忧郁越界,无脑转移即可
                dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i-1][j-1]
        
        return dp[n][m]

这里我们用了一个巧妙的方式,我们令,这是为了给绥化物流:动态计划两题连刷,移动下标的小技巧 第1张一个消耗为0的入口。这样当我们执行绥化物流:动态计划两题连刷,移动下标的小技巧 第2张的时刻,就会获得0,这样绥化物流:动态计划两题连刷,移动下标的小技巧 第3张就会自动完成,就不用我们在循环当中举行特判了。固然使用 if 特判也是可以的,然则这样写感受更简练一些。

末端

到这里,关于LeetCode 63和64两题就做完了,是不是很轻松呢?

在这两题的代码当中我们用到了两个技巧,一个是为了防止dp的时刻超界,而举行大量的判断,从而移动下标的技巧。另一个技巧是人为给初始位置提供一个初始选择入口的技巧。有了这两个技巧,可以大大简化我们编码的庞大度。否则你可能需要写许多分外的逻辑来特殊处置一些界限情形,这些界限情形往往庞大而且容易失足,因此能够制止是再好不外了。

今天的文章就到这里,原创不易,扫码关注我,获取更多精彩文章。

绥化物流:动态计划两题连刷,移动下标的小技巧 第4张

,

Sunbet

Sunbet www.sumeruminecraft.com Sunbet是Sunbet的大型娱乐网站,Sunbet简单快捷,业内口碑极好,是你的最佳选择。sunbet,就是要您玩得开心,赢得更开心!

转载声明:本站发布文章及版权归原作者所有,转载本站文章请注明文章来源:欧博亚洲(Allbet Game)!

本文链接:https://www.qzkaishanjx.com/post/809.html

网友评论