For the code below, which is used for Leetcode #64 Minimum Path Sum, I tried to make the cache grid using " len(grid)" and it does not work for all test cases, but if I do "for i in range(len(grid))" it works perfectly. I'm wondering why this makes a difference if the grid has the same dimensions either way. My code works for the first 2 cases but fails at the third, the code that uses range is accepted in Leetcode. Thank you.
class Solution:
def minPathSum(self, grid: list) -> int:
# cash = [[-1] * len(grid[0])] * len(grid)
cash = [[-1] * len(grid[0]) for i in range(len(grid))]
return self.recursion(grid, 0, 0, cash)
def recursion(self, grid, y, x, cash):
# first we check if the space is valid
if self.check(grid, y, x) is not True:
return 0
# then we check if that space has already been cached, if it has, we just return that space
if cash[y][x] != -1:
return cash[y][x]
# this is where the space currently is on the grid
current = grid[y][x]
# now check if we are currently at the rightmost or bottommost perimeters of the grid
if y == len(grid) - 1: # if at rightmost, have to go down
cash[y][x] = current + self.recursion(grid, y, x + 1, cash)
elif x == len(grid[0]) - 1: # at bottommost, have to go right
cash[y][x] = current + self.recursion(grid, y + 1, x, cash)
else: # if the current value is not at a bottom or right perimeter, keep going
cash[y][x] = current + min(self.recursion(grid, y, x + 1, cash), # compare the right block
self.recursion(grid, y + 1, x, cash)) # to the down block
print(cash)
return cash[y][x]
# check if this space exists in the grid using the grid boundaries
def check(self, grid, y, x):
return len(grid) > y >= 0 and len(grid[0]) > x >= 0
grid = [[1,3,1],[1,5,1],[4,2,1]]
print(Solution().minPathSum(grid=grid))
grid = [[1,2,3],[4,5,6]]
print(Solution().minPathSum(grid=grid))
grid = [[1,2],[1,1]]
print(Solution().minPathSum(grid=grid))
