• 注册
• 查看作者
• # LeetCode 64. Minimum Path Sum

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: 7Explanation: Because the path 1→3→1→1→1 minimizes the sum.```

```class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
h, w = len(grid), len(grid)

result = [[0 for i in range(w)] for j in range(h)]

result = grid

for i in range (1,w):
result[i] = result[i-1] + grid[i]
for i in range (1,h):
result[i] = result[i-1] + grid[i]
for i in range (1,h):
for j in range(1,w):
result[i][j] = min(result[i-1][j],result[i][j-1]) + grid[i][j]
return result[h-1][w-1]
print(result)```

[[0,0,0]      [[1,0,0]        [[1,4,5]       [[1,4,5]        [[1,4,5]

[0,0,0] →   [0,0,0]  →    [0,0,0]  →  [2,0,0]   →   [2,0,0]

[0,0,0]]      [0,0,0]]        [0,0,0]]       [6,0,0]]        [6,0,0]]

compare up-left for minimum,

and add original till the end

纽约州·法拉盛
• 0
• 0
• 0
• 334
• 请登录之后再进行评论

• 做任务
• 全部清空
•   