很简单
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.
Subscribe to see which companies asked this question
Show Tags
Show Similar Problems
#F[i][j] = min{F[i-1][j],F[i][j-1]} + m[i][j]
class Solution(object):
"""
:type grid: List[List[int]]
:rtype: int
"""
def minPathSum(self, grid):
list = []
for i in range(len(grid)):
list.append([])
for i in range(len(grid)):
for j in range(len(grid[i])):
if i==0:
if j == 0:
list[i].append(grid[i][j])
else:
list[i].append(list[i][j-1] + grid[i][j])
else:
if j == 0:
list[i].append(grid[i][j] + list[i-1][j])
else:
list[i].append(min(list[i-1][j],list[i][j-1]) + grid[i][j])
return list[-1][-1]
