For each cell (i,j) you need to check the optimal solution at above (i-1,j) and the one to the left (i,j-1) since one can only move down or to the right. O(mn) complexity with O(n) space.

```
def minPathSum(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
if not grid: return 0
m,n = len(grid), len(grid[0])
prevrow = [0]*(n+1)
prevrow[0] = float('inf')
for j in range(1,n+1):
prevrow[j] = sum(grid[0][:j])
if m == 1: return prevrow[n]
for i in range(1,m):
currrow = [0]*(n+1)
currrow[0] = float('inf')
for j in range(1,n+1):
currrow[j] = min(prevrow[j], currrow[j-1]) + grid[i][j-1]
prevrow = currrow
return currrow[n]
```