LeetCode 64. Minimum Path Sum

Description

https://leetcode.com/problems/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.

Explanation

dp(i,j)=grid(i,j)+min(dp(i+1,j),dp(i,j+1))

Python Solution

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        
        min_paths = [[0 for j in range(0, len(grid[0]))] for i in range(0, len(grid))]

        min_paths[0][0] = grid[0][0]
        for j in range(1, len(grid[0])):
            min_paths[0][j] = min_paths[0][j - 1] + grid[0][j]

        for i in range(1, len(grid)):
            min_paths[i][0] = min_paths[i - 1][0] + grid[i][0]
            
        
        for i in range(1, len(grid)):
            for j in range(1, len(grid[0])):
                min_paths[i][j] = min(min_paths[i][j - 1], min_paths[i - 1][j]) + grid[i][j]
        
                
        return min_paths[len(grid) - 1][len(grid[0]) - 1]
        

• Time complexity: O(MN). We traverse the entire matrix once.
• Space complexity: O(MN). Another matrix of the same size is used.