Problem Statement in English

You’re given an m x n grid filled with non-negative numbers. Find a path from the top left to the bottom right, which minimizes the sum of all numbers along its path.

Approach

We can use dynamic programming to solve this problem. The idea is to build up the solution by calculating the minimum path sum to each cell in the grid. The solution to each cell depends on the minimum path sum to the last cell in the grid by going either down or right.

And we’re done!

Solution in Python


class Solution:
    def minPathSum(self, grid: list[list[int]]) -> int:
        m = len(grid)        
        n = len(grid[0])

        @cache
        def dp(i, j):
            if i == m - 1 and j == n - 1:
                return grid[i][j]

            res = inf
            
            if i + 1 < m:
                res = min(res, grid[i][j] + dp(i + 1, j))
            if j + 1 < n:
                res = min(res, grid[i][j] + dp(i, j + 1))

            return res

        return dp(0, 0)

Complexity

  • Time: $O(m \times n)$
    Since we are visiting each cell in the grid once, the time complexity is proportional to the number of cells in the grid, which is m * n.

  • Space: $O(m \times n)$
    Since we are using memoization to store the results of subproblems, the space complexity is also proportional to the number of cells in the grid, which is m * n.

And we are done.