64. Minimum Path Sum

• categories: Code, Interview Question, leetcode, Medium
• source: https://leetcode.com/problems/minimum-path-sum
• topics: Dynamic Programming

Description

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.

Idea

• Dynamic Programming

Code

Down Top

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        for j in range(1, cols):
            grid[0][j] += grid[0][j-1]
        for i in range(1, rows):
            grid[i][0] += grid[i-1][0]
 
        for i in range(1, rows):
            for j in range(1, cols):
                grid[i][j] += min(grid[i-1][j], grid[i][j-1])
 
        return grid[-1][-1]

Top Down - slow because of recursion

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        @cache
        def dp(i, j):
            if i == 0 and j == 0:
                return grid[i][j]
            if i == 0:
                return grid[i][j] + dp(i,j-1)
            if j == 0:
                return grid[i][j] + dp(i-1,j)
            return grid[i][j] + min(dp(i-1,j), dp(i,j-1))
        return dp(len(grid)-1, len(grid[0])-1)