64.md

64. 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.

Example 1:
[[1,3,1],
 [1,5,1],
 [4,2,1]]
Given the above grid map, return 7. Because the path 1→3→1→1→1 minimizes the sum.

my thoughts:

1. dp. 2d dp is straight forward. 1d dp needs a little tweek.
time: O(n*m); 	space: O(n*m) --2d
	  O(n*m);		   O(n)   --1d

my solution:

**********103 ms
class Solution:
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        if not grid:
            return 0
        w = len(grid[0])
        h = len(grid)
        dp = [grid[0][0]]
        for i in range(1, w):
            dp.append(dp[i-1]+grid[0][i])
            
        for i in range(1, h):
            dp[0] += grid[i][0]
            for j in range(1, w):
                dp[j] = grid[i][j] + min(dp[j-1], dp[j])
                
        return dp[-1]

my comments:

from other ppl's solution:

1. N/A