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.
Eg: [1,3,1],[1,5,1],[4,2,1]]
Given the above grid map, return 7. Because the path 1→3→1→1→1 minimizes the sum.
My solution using recursion but it is wrong, please help me correct it and explain what am I missing.
import math
def minPath(grid,n,m,a,b):
if n>a or m>b:
return math.inf
grid[n][m] += min(minPath(grid,n+1,m,a,b),minPath(grid,n,m+1,a,b))
return grid[n][m]
def minPathSum(grid):
m = len(grid) - 1
n = len(grid[0]) - 1
a = m-1
b= n-1
minPath(grid,0,0,a,b)
return grid[a][b]
print(minPathSum([[1,3,1],[1,5,1],[4,2,1]]))