leetcode 【 Minimum Path Sum 】python 实现

题目：

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 row
11         tmp_sum = 0
12         for i in range(len(grid[0])):
13             tmp_sum = tmp_sum + grid[0][i]
14             step_matrix[0][i] = tmp_sum
15         # first line
16         tmp_sum = 0
17         for i in range(len(grid)):
18             tmp_sum = tmp_sum + grid[i][0]
19             step_matrix[i][0] = tmp_sum
20         # dynamic program other positions in gird
21         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 path
25         return step_matrix[len(grid)-1][len(grid[0])-1]

思路：

动态规划常规思路。详情见http://www.cnblogs.com/xbf9xbf/p/4250359.html这道题。

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

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