Day 18 - Minimum Path Sum

Solution.py

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        dp = [[0 for col in range(len(grid[0]))] for row in range(len(grid))]
        lastCol = len(grid[0]) - 1
        lastRow = len(grid) - 1
        
        dp[lastRow][lastCol] = grid[lastRow][lastCol]
        
        # Populate the right-most column
        for row in reversed(range(len(grid) - 1)):
            dp[row][lastCol] = dp[row + 1][lastCol] + grid[row][lastCol]
                          
        # Populate the bottom row
        for col in reversed(range(len(grid[0]) - 1)):
            dp[lastRow][col] = dp[lastRow][col + 1] + grid[lastRow][col]
            
        for row in reversed(range(len(grid) - 1)):
            for col in reversed(range(len(grid[0]) - 1)):
                dp[row][col] = min(dp[row + 1][col], dp[row][col + 1]) + grid[row][col]
        
        return dp[0][0]