[Leetcode][python]Minimum Path Sum
[Leetcode][python]Minimum Path Sum
蛮三刀酱
发布于 2019-03-26 16:19:41
发布于 2019-03-26 16:19:41
题目大意
从一个矩阵的左上角出发到右下角，只能向右或向下走，找出哪一条路径上的数字之和最小。
注意点： 所有数字都是非负的
解题思路
动态规划，承接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]总结
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017年10月14日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录