问题描述：

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.

算法：

我首先想到的是利用优先队列进行搜索。

import heapq


class Solution(object):


    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        endx = len(grid) - 1
        endy = len(grid[0]) - 1
        priority_que = [(grid[0][0], (0,0))]
        while True:
            curSum, point = heapq.heappop(priority_que)
            if point == (endx,endy):
                return curSum
            curX,curY = point
            successors = [(x,y)for (x,y) in [(curX+1, curY), (curX, curY+1)] if x<=endx and y<=endy]
            for x,y in successors:
                if (x,y) == (endx,endy):
                    return curSum+grid[x][y]
                else:
                    heapq.heappush(priority_que, (curSum+grid[x][y],(x,y)))

但是，提交代码后发现超时。
这时，首先想到的是动态规划。
状态转移方程为 func(x,y) = min(func(x-1,y),func(x,y-1))+grid(x,y)
使用矩阵存储从起点到当前位置的路径最小值，从最上面一层以及最左面一层，逐渐递推到结束位置。

class Solution(object):


    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        endx = len(grid)
        endy = len(grid[0])
        path = [[0 for _ in range(endy)] for _ in range(endx)]
        path[0][0] = grid[0][0]
        # get up line ready
        for i in range(1, endy):
            path[0][i] = path[0][i-1] + grid[0][i]
        # get left line ready
        for i in range(1, endx):
            print(path)
            print(i)
            path[i][0] = path[i-1][0] + grid[i][0]


        for r in range(1, endx):
            for c in range(1, endy):
                path[r][c] = min(path[r-1][c], path[r][c-1]) + grid[r][c]
        return path[endx-1][endy-1]