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.
Solution:
class Solution: # @param grid, a list of lists of integers # @return an integer def minPathSum(self, grid): if len(grid)==0 or len(grid[0])==0: return 0 for row in range(0, len(grid)): for col in range(0, len(grid[0])): if row>0 and col>0: grid[row][col] += min(grid[row-1][col],grid[row][col-1]) elif row>0: grid[row][col] += grid[row-1][col] elif col>0: grid[row][col] += grid[row][col-1] return grid[len(grid)-1][len(grid[0])-1]
No comments :
Post a Comment