Leetcode Problem 64 Minimum Path Sum.txt

64. Minimum Path Sum
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.


Hint to solve: Use dynamic programming. for every cell the min value would be min(topCell, leftCell) + currentCell


class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        
        matrix = [[sys.maxsize for _ in range(0,len(grid[0]) + 1)] for x in range(len(grid) + 1)]        
        matrix[0][1] = 0
        matrix[1][0] = 0
        
        for row in range(1,len(matrix)):
            for col in range(1, len(matrix[0])):
                matrix[row][col] = min(matrix[row-1][col], matrix[row][col-1]) + grid[row-1][col-1]
                
        return matrix[len(grid)][len(grid[0])]