"""

let's reset the array by it's min value start out from (0,0)

in another words, after reset

grid[i][j]'s value will be the min value start out from (0,0)

if we are at (i,j), we will be either from (i-1,j) or (i,j-1)

we call them s1 and s2, let's assume they are both in range

grid[i][j] will be grid[i][j]+min(s1, s2)

we will start out from (0,0) and reset the entire grid.

"""

class Solution(object):

def minPathSum(self, grid):

n = len(grid)

m = len(grid[0])

for i in xrange(n):

for j in xrange(m):

s1 = s2 = float('inf')

if i-1>=0:

s1 = grid[i-1][j]

if j-1>=0:

s2 = grid[i][j-1]

if s1==float('inf') and s2==float('inf'): continue #both source out of range

grid[i][j]+=min(s1, s2)

return grid[-1][-1]