【动态规划】【leetcode】64. Minimum Path Sum

1. 题目描述

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.
Example

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

2. 算法分析

假设我们从(0,0)开始沿某一条路径到达位置(i,j)处,获得最小的和。我们把这个和记为f(i,j)。那么针对f(i,j)有下面两条规则

  1. 首先,如果i,j均为0的话,那么显然f(0,0) = grid[0][0]
  2. 因此题目规定,路径只能向右或者向下。那么想要到达(i,j)这个位置,必须先到达(i-1,j)处或者(i, j-1)处。因此到达(i,j)的最小路径和应该是f(i,j) = min{f(i -1, j), f(i, j - 1 )} + grid[i][j]
    基于这两条规则,我们可以写出代码

3.代码实现1

class Solution():
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        row = len(grid)
        # 防止输入grid == []
        if (row == 0):
            return 0    
        # 防止输入grid == [[]]
        colum = len(grid[0])
        if (row == 0 or colum == 0):
            return 0
        res = [[0 for i in range(colum)] for j in range(row)] 
        for i in range(row):
            for j in range(colum):
                if (i == 0 and j == 0):
                    res[i][j] = grid[0][0]
                else:
                    if i == 0:
                        res[i][j] = res[i][j - 1] + grid[i][j]
                    elif j == 0:
                        res[i][j] = res[i - 1][j] + grid[i][j]
                    else:
                        res[i][j] = min(res[i - 1][j], res[i][j - 1]) + grid[i][j]
        return res[row - 1][colum - 1]

grid = [[1,3,1],[1,5,1],[4,2,1]]
res = Solution()
ans = res.minPathSum(grid)

在这段代码当中,我们初始化了一个跟grid维度一样的二维列表,用这个列表来记录到达(i,j)位置的最小路径和。事实上,直接在原来的grid列表中记录就可以了,完全没有必要申请这样一个列表,这样可以大幅提高速度,同时节省内存空间。这个在当时刷题时没有想到。那么我们可以把代码改进一下

代码实现2(改进)

class Solution():
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        row = len(grid)
        if (row == 0):
            return 0    
        colum = len(grid[0])
        if (row == 0 or colum == 0):
            return 0 
        for i in range(row):
            for j in range(colum):
                if (i == 0 and j == 0):
                    continue
                else:
                    if i == 0:
                        grid[i][j] = grid[i][j - 1] + grid[i][j]
                    elif j == 0:
                        grid[i][j] = grid[i - 1][j] + grid[i][j]
                    else:
                        grid[i][j] = min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j]
        return grid[row - 1][colum - 1]

grid = [[1,3,1],[1,5,1],[4,2,1]]
res = Solution()
ans = res.minPathSum(grid)
print(ans);        
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-24 13:35
点赞 评论 收藏
分享
机械打工仔:不管啥专业,找工作改简历的第一课先把你那排版改了,简历上不要写个人简历四个字,找你要简历的谁不知道这个是简历?而且还占那么多空间,直接把自己名字和基础信息写上面,整体字体大一些。 还有这种经典两页简历一页大空白,导出PDF的时候多了一页几乎全是白的你自己看着不难受吗随手的事为啥不能改掉呢,这是态度问题,你试想一下你是HR你打开简历看到格式都没调整过会是什么感受?你自己都不重视你的简历,HR更不会在意。 然后内容你那个做两年咖啡就别往里写了,简历在精不在多,你在往你的简历里打字的时候就要想好这东西对你要找的工作有没有帮助。自我评价写一行就行了,不如给专业技能单开一栏。核心课程均分90这个真别写了,把你上过的有用的专业课列出来也行。有很多地方废话很多的精炼一下,比如你校内项目第一个写的那些,全然没有重点。 好好修改一下,我看你内容也挺优秀的,别被一个随便做的简历耽误了,我一个同专业的打工人看了都揪心更别说一天看几百份简历的HR
听劝,我这个简历该怎么改...
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-23 14:22
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务