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:
Input: [ [1,3,1], [1,5,1], [4,2,1] ] Output: 7 Explanation: Because the path 1→3→1→1→1 minimizes the sum.
My code:
import numpy as np
class Solution:
def minPathSum(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
if len(grid)==0:
return 0
self.m=len(grid)
example=grid[0]
if len(example)==0:
return 0
self.n=len(example)
self.matrix=np.zeros([self.m,self.n])-1
result=self.Sum(0,0,grid)
#print(self.matrix)
return int(result)
def Sum(self,i,j,grid):
if i==self.m or j==self.n:
return 0
if self.matrix[i,j]!=-1:
return self.matrix[i,j]
if i==self.m-1:
result=0
for k in range(j,self.n):
result+=grid[i][k]
self.matrix[i,j]=result
return result
if j==self.n-1:
result=0
for k in range(i,self.m):
result+=grid[k][j]
self.matrix[i,j]=result
return result
result1=self.Sum(i+1,j,grid)
result2=self.Sum(i,j+1,grid)
self.matrix[i,j]=grid[i][j]+min([result1,result2])
return self.matrix[i,j]