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.

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]