Minimum Path Sum

Patrick Leaton
Published: Nov. 6, 2021, 5 p.m.
Problem 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.

 

Example 1:

Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.

Example 2:

Input: grid = [[1,2,3],[4,5,6]]
Output: 12

 

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 200
  • 0 <= grid[i][j] <= 100

 

The description was taken from https://leetcode.com/problems/minimum-path-sum/.

Problem Solution

#O(M*N) Time, O(M*N) Space
class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
       
        dp = [[0]*n for rows in range(0,m)]
        dp[0][0] = grid[0][0]
       
        for row in range(1, m):
            dp[row][0] = grid[row][0] + dp[row-1][0]
       
        for col in range(1, n):
            dp[0][col] = grid[0][col] + dp[0][col-1]
       
        for row in range(1, m):
            for col in range(1, n):
                dp[row][col] = grid[row][col] + min(dp[row-1][col], dp[row][col-1])
       
        return dp[-1][-1]

Problem Explanation

This problem is a variation of Unique Paths.

Instead of looking for the maximum number of paths to the bottom-right corner, however, we are looking for the minimum path to get there.

This question falls in line with other problems that require finding a combination sum like Decode Ways, Climbing Stairs, House Robber, Paint the Fence.

To solve these problems, we will arrive at point B and look back at each potential point A that we got here from, and add the combinations from our point A's to point B.

For this problem, we can create a dp cache equal to the size of the grid and for each cell, we can increment the current cell with the minimum path from either the top or left cell, since we can only step down or to the right.

Once we have traversed the grid, our answer will be in the last cell of the dp cache.

Let's start by saving the length and width of our grid to variables m and n.

        m, n = len(grid), len(grid[0])

 

Then, we will create our dp cache equal to the size of the grid.

We could also convert this to a constant space solution by skipping the cache and just tabulating each cell from the grid in-place, but that may be considered a cheating approach and it doesn't fall in line with traditional Dynamic Programming methods.

        dp = [[0]*n for rows in range(0,m)]

 

Now we can begin setting our base cases.

If the input grid was only one cell, then the minimum path from the first cell to the last cell would be the value in that single cell.

        dp[0][0] = grid[0][0]

 

If the input grid was only one column, then the minimum path for each row within that column would be the only path.  That path would be the path that was traveled from the cell directly above it.

        for row in range(1, m):
            dp[row][0] = grid[row][0] + dp[row-1][0]

 

Similarly, if the input grid was only one row, then the minimum path for each column within that row would be the only path.  That path would be the path that was traveled from the cell directly to the left of it.

        for col in range(1, n):
            dp[0][col] = grid[0][col] + dp[0][col-1]

 

Now that we have our base cases solved, we will traverse the grid excluding our base cases and for each cell in our dp cache, we will increment it by the current cell in the grid plus the minimum between the top and left cells from the cache.

        for row in range(1, m):
            for col in range(1, n):
                dp[row][col] = grid[row][col] + min(dp[row-1][col], dp[row][col-1])

 

When we have finished our traversal, the minimum path to the last cell will be stored in the last cell of the cache.

        return dp[-1][-1]

 

Additional Notes

Since we are only using one row to store the number of paths for each subproblem, we only need to create a one-dimensional array to store the result, and we will just pass over it m - 1 times.

Each pass through the dp array, we will be partitioning the subproblems as "solved" for the range of index one to index two, index one to index three, index one to index four, ... index one to index m, just like we would for other traditional bottom-up dynamic programming problems that utilize a one-dimensional array to hold subproblem answers, like Unique Paths.

Here we can create a dp cache, set the base case for if we only had a single row as an input and then set the base case for if we only had one column, the first column, during each additional subproblem iteration.

We can then choose the minimum path from the previous element and the current element to sum with the current cell from the grid to answer each subproblem, as that would be indicative of the top and left paths.

#O(M*N) Time, O(N) Space
class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        
        dp = [0] * len(grid[0])
        dp[0] = grid[0][0]
        
        for i in range(1, len(dp)):
            dp[i] = grid[0][i] + dp[i-1]
        
        for row in range(1, m):
            dp[0] += grid[row][0]
            for col in range(1, n):
                dp[col] = grid[row][col] + min(dp[col-1], dp[col]) 
                
        return dp[-1]