# Leetcode: Minimum Path Sum

Minimum Path Sum Similar Problems:

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

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

```## Blog link: https://code.dennyzhang.com/minimum-path-sum
## Basic Ideas:
##           For point grid[i][j], think about the prevoius step of the minimize path
##           It should come from either grid[i-1][j] or grid[i][j-1].
##
##           So f(i, j) can be calculated from f(i-1, j) and f(i, j-1)
##
##           Do we have to use the extra space to save the intermediate results?
##           No, we can reuse the original matrix
##
## Complexity: Time O(m*n), Space O(1)
##
class Solution(object):
def minPathSum(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
m = len(grid)
if m == 0: return 0
n = len(grid)
for i in xrange(m):
for j in xrange(n):
# skip the first node
if i == 0 and j == 0:
continue
# first column
if j == 0:
grid[i][j] += grid[i-1][j]
continue
# first row
if i == 0:
grid[i][j] += grid[i][j-1]
continue
grid[i][j] = min(grid[i][j-1], grid[i-1][j]) + grid[i][j]

return grid[-1][-1]
```

Share It, If You Like It.