Minimum Path Sum

Dynamic Programming2D Matrix

20 min

Problem Statement

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.

You can only move either down or right at any point in time.

Example

Example 1:

Output: 7

Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.

Solution

This problem is another classic for dynamic programming. We can solve it by creating a DP grid where each cell `dp[i][j]` stores the minimum sum to reach that cell from the top-left corner.

The minimum path sum to any cell `(i, j)` is the value of that cell plus the minimum of the path sums from the cell above (`i-1, j`) and the cell to the left (`i, j-1`). This builds upon the solutions of subproblems to find the final answer.

Algorithm Steps (DP)

Create a DP grid of the same size as the input grid.
Initialize the top-left cell `dp[0][0]` with `grid[0][0]`.
Fill the first row: `dp[0][j] = dp[0][j-1] + grid[0][j]`.
Fill the first column: `dp[i][0] = dp[i-1][0] + grid[i][0]`.
Iterate through the rest of the grid from `(1, 1)`.
For each cell `(i, j)`, calculate `dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])`.
The final answer is the value in the bottom-right cell, `dp[m-1][n-1]`.

Minimum Path Sum DP Grid

Progress1 / 1

Ready to start.

Minimum Path Sum (DP)


class Solution:
    def minPathSum(self, grid: list[list[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [[0] * n for _ in range(m)]
        dp[0][0] = grid[0][0]

        for i in range(1, m):
            dp[i][0] = dp[i-1][0] + grid[i][0]
        
        for j in range(1, n):
            dp[0][j] = dp[0][j-1] + grid[0][j]
            
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
                
        return dp[m-1][n-1]