LintCode Q110 Minimum Path Sum in Python

  • Jinhai ZHOU
  • 3 Minutes
  • 2016年12月11日
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
"""
@param grid: a list of lists of integers.
@return: An integer, minimizes the sum of all numbers along its path
"""
def minPathSum(self, grid):
# write your code here
if len(grid) == 0 or len(grid[0]) == 0:
return 0
m = len(grid)
n = len(grid[0])
dp = [[0]*n for i in xrange(m)]
dp[0][0] = grid[0][0]
for col in xrange(1, n): # i is col
dp[0][col] = dp[0][col - 1] + grid[0][col]
for row in xrange(1, m): # j is row
dp[row][0] = dp[row - 1][0] + grid[row][0]
for row in xrange(1, m):
for col in xrange(1, n):
dp[row][col] = min(dp[row][col - 1], dp[row - 1][col]) + grid[row][col]
return dp[-1][-1]
知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。