```
class Solution(object):
def minPathSum(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
if not grid:
return 0
pre = [0]*len(grid)
n = len(grid)
m = len(grid[0])
pre[-1] = grid[-1][-1]
for i in range (n-2, -1, -1):
pre[i] = grid[i][m-1] + pre[i+1]
for i in range (len(grid[0])-2,-1,-1):
cur = [0]*len(grid)
cur[-1] = grid[-1][i]+pre[-1]
for j in range (len(grid)-2,-1,-1):
cur[j] = min(cur[j+1], pre[j])+grid[j][i]
pre=cur[:]
return pre[0]
```