LC 0064 [M] Minimum Path Sum - ALawliet/algorithms GitHub Wiki

the min cost to get to the current is the cell min of the cost of the cells we took to get there from the up or left (down or right if backwards) - the cost we incurred so far

the forward solution is most intuitive just for this but the backwards adding solution transitions best to Dungeon Game follow-up:

[[ 1   3   1]
 [ 1   5   1]
 [ 4   2   1]]

[[ 7.  6.  3. inf]
 [ 8.  7.  2. inf]
 [ 7.  3.  1.  0.]
 [inf inf  0. inf]]

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0])

        T = [ [0 for c in range(cols)] for r in range(rows) ]
        
        T[0][0] = grid[0][0]
        for r in range(1, rows):
            T[r][0] = T[r-1][0] + grid[r][0]
        for c in range(1, cols):
            T[0][c] = T[0][c-1] + grid[0][c]

        for r in range(1, rows):
            for c in range(1, cols):
                T[r][c] = min(T[r-1][c], T[r][c-1]) + grid[r][c]
                
        return T[-1][-1]

    def backwardsPadding(self, grid: List[List[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0])

        T = [ [float('inf') for c in range(cols + 1)] for r in range(rows + 1) ]

        T[-2][-1] = T[-1][-2] = 0

        for r in range(rows - 1, -1, -1):
          for c in range(cols - 1, -1, -1):
            T[r][c] = min(T[r+1][c], T[r][c+1]) + grid[r][c]

        return T[0][0]

T/S: O(num rows * num cols)