您的位置:必赢娱乐网站是多少啊 > 星座解说 > 大方格的最小路径一定会路过小方格最小路径吗

大方格的最小路径一定会路过小方格最小路径吗

2019-10-14 11:20

{"type":3,"value":{"videosourcetype":1,"vid":"o09068rdzf5","desc":"星座转败为胜图鉴!魏无羡X韩国商人言X蓝湛X吕归尘成人事教育育头","img":"

Minimum Path Sum

题意:

  给定一个方格,各种格子中有贰个数字,今后大家要找一条从方格左上角出发直到方格右下角的路,条件是那条路经过的数字之和为最小。

 

解题思路:

  此题依旧是动态规划项指标难点,关键是大家什么样将以此主题素材分开为多少个八九不离十阶段。

  最近的主张是同意可以先找到小方格内的微小路线,然后在去行使当前的结果去找比她大的方格的细微路线。就算是那样的话,大方格的纤维路径一定会经过小方格最小路线吗?(一定会达到小方格的左上角呢?)那或多或少还不可能鲜明。

  从刚刚的主见作者衍生出来另一种方法,首先我们着重大家每一步影响到的方块数,大家会意识随着路线长度的充实,我们是以阶梯形状向上推动的(借使大家从右下方往左上方找)。像这么:

OOO   OOO   OOX   OXX   XXX

OOO > OOX > OXX > XXX > XXX

OOX   OXX   XXX   XXX   XXX

  根据动态规划的牵挂,在种种阶段,大家得以将打叉的区域的方格数字符号为从右下角出发达到当前方格的最短路线长度。层层递增,那么有方今 

matrix[i][j] = min(matrix[i-1][j], matrix[i][j-1])

  若是大家有二个矩阵如下:

S50

160

43E

  那么首先大家先更新矩阵右下角两条边的最短路线,然后在逐个往上立异矩阵:

S50   S50   S50   (S+5)50

160 > 190 > 890 >   8  90

73E   73E   73E     7  3E

  于是程序大家就可写成:

 

class Solution:
    # @param {integer[][]} grid
    # @return {integer}
    def minPathSum(self, grid):
        m = len(grid)
        n = len(grid[0])
        for i in range(1,m):
            grid[i][0] += grid[i-1][0]
        for j in range(1,n):
            grid[0][j] += grid[0][j-1]
        for i in range(1,m):
            for j in range(1,n):
                grid[i][j] += min(grid[i-1][j], grid[i][j-1])
        return grid[-1][-1]

 

本文由必赢娱乐网站是多少啊发布于星座解说,转载请注明出处:大方格的最小路径一定会路过小方格最小路径吗

关键词: