```
class Solution(object):
def minPathSum(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
m, n = len(grid), len(grid[0])
dp = [[sys.maxint]*(n+1) for _ in range(m+1)]
dp[0][1] = 0
for i in range(1, m+1):
for j in range(1, n+1):
dp[i][j] = grid[i-1][j-1] + min(dp[i][j-1], dp[i-1][j])
return dp[-1][-1]
```

- O(mn) in time, O(n) in space:

```
class Solution(object):
def minPathSum(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
m, n = len(grid), len(grid[0])
dp = [sys.maxint] * (n+1) # dp[i] means min path sum for previous row to col i-1
dp[1] = 0
for i in range(1, m+1):
dp[1] += grid[i-1][0]
for j in range(2, n+1):
dp[j] = grid[i-1][j-1] + min(dp[j-1], dp[j])
return dp[-1]
```