题目：

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.

 

代码：oj测试通过 Runtime: 102 ms

1 class Solution: 2     # @param grid, a list of lists of integers 3     # @return an integer 4     def minPathSum(self, grid): 5         # none case 6         if grid is None: 7             return None 8         # store each step on matrix 9         step_matrix=[[0 for i in range(len(grid[0]))] for i in range(len(grid))]10         # first row11         tmp_sum = 012         for i in range(len(grid[0])):13             tmp_sum = tmp_sum + grid[0][i]14             step_matrix[0][i] = tmp_sum15         # first line16         tmp_sum = 017         for i in range(len(grid)):18             tmp_sum = tmp_sum + grid[i][0]19             step_matrix[i][0] = tmp_sum20         # dynamic program other positions in gird21         for row in range(1,len(grid)):22             for col in range(1,len(grid[0])):23                 step_matrix[row][col]=grid[row][col]+min(step_matrix[row-1][col],step_matrix[row][col-1])24         # return the minimun sum of path25         return step_matrix[len(grid)-1][len(grid[0])-1]

 

思路：

动态规划常规思路。详情见这道题。

需要注意的是，动态规划迭代条件step_matrix[][]=grid[][]+min(...)

min里面的一定要是step_matrix对应位置的元素。一开始写成grid对应的元素，第一次没有AC，修改后第二次AC了。