[Leetcode][python]Minimum Path Sum

布满荆棘的人生 2022-06-07 07:14 131阅读 0赞

## 题目大意 ##

从一个矩阵的左上角出发到右下角，只能向右或向下走，找出哪一条路径上的数字之和最小。

注意点：  
所有数字都是非负的

## 解题思路 ##

动态规划，承接[http://blog.csdn.net/qqxx6661/article/details/78231730][http_blog.csdn.net_qqxx6661_article_details_78231730]  
不过从计算到达该点有多少种走法转变为求最小和为多少。找出上面和左边格子的最小值加上当前格子中的数字即可。

dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

## 代码 ##

class Solution(object):
        def minPathSum(self, grid):
            """
            :type grid: List[List[int]]
            :rtype: int
            """
            m = len(grid)
            n = len(grid[0])
            dp = [[0 for __ in range(n)] for __ in range(m)]
            dp[0][0] = grid[0][0]
            for i in range(1, m):
                dp[i][0] = dp[i-1][0] + grid[i][0]
            for i in range(1, n):
                dp[0][i] = dp[0][i-1] + grid[0][i]
            for i in range(1, m):
                for j in range(1, n):
                    dp[i][j] = min(dp[i-1][j] + grid[i][j], dp[i][j-1] + grid[i][j])
            return dp[-1][-1]

## 总结 ##

[http_blog.csdn.net_qqxx6661_article_details_78231730]: http://blog.csdn.net/qqxx6661/article/details/78231730

发表评论取消回复

表情：

评论列表（有 0 条评论，131人围观）

还没有评论，来说两句吧...

相关阅读

相关 Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom

- 日理万妓/ 2022年09月26日 03:11/ 0 赞/ 106 阅读

相关 112. Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that a

绝地灬酷狼/ 2022年07月15日 01:19/ 0 赞/ 178 阅读

相关 [leetcode]: 112. Path Sum

1.题目 Given a binary tree and a sum, determine if the tree has a root-to-leaf path suc

野性酷女/ 2022年06月15日 11:40/ 0 赞/ 191 阅读

相关 112. Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that a

本是古典何须时尚/ 2022年05月04日 08:30/ 0 赞/ 191 阅读

相关 64. Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom

╰半橙微兮°/ 2022年04月21日 22:08/ 0 赞/ 172 阅读

相关 113. Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals

冷不防/ 2022年03月26日 09:26/ 0 赞/ 199 阅读

相关 113. Path Sum II

class Solution { public List<List<Integer>> pathSum(TreeNode root, int sum)

￡神魔★判官ぃ/ 2021年12月22日 06:53/ 0 赞/ 195 阅读

相关 Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals

系统管理员/ 2021年12月17日 10:33/ 0 赞/ 198 阅读

相关 [Leetcode] Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom

超、凢脫俗/ 2021年12月03日 07:19/ 0 赞/ 182 阅读

相关 437. Path Sum III

You are given a binary tree in which each node contains an integer value. Find the numb

古城微笑少年丶/ 2021年11月29日 18:40/ 0 赞/ 196 阅读