Leetcode 64. Minimum Path Sum

 64. Minimum Path Sum

Medium, Dynamic Programming

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] <= 200

The problem Minimum Path Sum asks for the minimum sum of a path from the top-left corner to the bottom-right corner in a grid, where the robot can only move right or down. The goal is to find the path that minimizes the sum of numbers along its way.

Approach 1: Dynamic Programming

Explanation:

We can solve this problem using dynamic programming (DP). The idea is to maintain a DP table (dp) where dp[i][j] represents the minimum path sum to reach the cell (i, j).

Steps:

1. Initialization:

   • The value at dp[0][0] is the value of the top-left cell (grid[0][0]), because this is the starting point.

2. First Row and First Column:

   • For the first row (i = 0), the only way to move is from the left, so we sum up the values from the previous cells in the row:

     dp[0][j] = dp[0][j - 1] + grid[0][j]
     

   • For the first column (j = 0), the only way to move is from the top, so we sum up the values from the previous cells in the column:

     dp[i][0] = dp[i - 1][0] + grid[i][0]
     

3. Filling the DP Table:

   • For each other cell (i, j), the minimum sum to reach that cell is the minimum of the sum of the top cell (dp[i-1][j]) and the left cell (dp[i][j-1]) plus the current cell's value:

     dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
     

4. Final result:

   • The value at dp[m-1][n-1] will be the minimum path sum from the top-left corner to the bottom-right corner.

Code:

public class Solution {
    public int MinPathSum(int[][] grid) {
        int m = grid.Length;
        int n = grid[0].Length;
        
        // Create a dp array to store the minimum sum at each cell
        int[,] dp = new int[m, n];
        
        // Initialize the starting cell (top-left corner)
        dp[0, 0] = grid[0][0];
        
        // Fill the first row (can only come from the left)
        for (int j = 1; j < n; j++) {
            dp[0, j] = dp[0, j - 1] + grid[0][j];
        }
        
        // Fill the first column (can only come from above)
        for (int i = 1; i < m; i++) {
            dp[i, 0] = dp[i - 1, 0] + grid[i][0];
        }
        
        // Fill the rest of the dp table
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i, j] = Math.Min(dp[i - 1, j], dp[i, j - 1]) + grid[i][j];
            }
        }
        
        // The bottom-right corner will contain the minimum path sum
        return dp[m - 1, n - 1];
    }
}

Time Complexity:

• Time Complexity: $O(m \times n)$, because we iterate through the entire grid to fill the DP table.
• Space Complexity: $O(m \times n)$, because we use a 2D array to store the intermediate results.

---

Approach 2: Space Optimization (Using 1D DP Array)

Explanation:

Just like in the Unique Paths problem, we can optimize the space complexity by using a 1D array instead of a 2D array. Each row only depends on the current and previous rows, so we can reduce the space to $O(n)$ by reusing a 1D array to store intermediate results.

Steps:

1. Use a 1D array dp where dp[j] represents the minimum path sum to reach cell (i, j) in the current row.
2. For each row, update the dp array by considering the minimum path from the cell above it or the cell to the left of it.

Code:

public class Solution {
    public int MinPathSum(int[][] grid) {
        int m = grid.Length;
        int n = grid[0].Length;
        
        // Create a dp array for space optimization
        int[] dp = new int[n];
        
        // Initialize the first cell
        dp[0] = grid[0][0];
        
        // Fill the first row (can only come from the left)
        for (int j = 1; j < n; j++) {
            dp[j] = dp[j - 1] + grid[0][j];
        }
        
        // Fill the rest of the dp array row by row
        for (int i = 1; i < m; i++) {
            // Update the first column of each row (can only come from above)
            dp[0] += grid[i][0];
            
            // Update the rest of the dp array
            for (int j = 1; j < n; j++) {
                dp[j] = Math.Min(dp[j], dp[j - 1]) + grid[i][j];
            }
        }
        
        // The last element in dp is the answer
        return dp[n - 1];
    }
}

Time Complexity:

• Time Complexity: $O(m \times n)$, because we still iterate over the grid but now use a 1D array.
• Space Complexity: $O(n)$, because we only use a 1D array to store the results for the current row.

---

Summary:

Approach	Time Complexity	Space Complexity	Explanation
Dynamic Programming (2D)	$O(m \times n)$	$O(m \times n)$	Uses a 2D DP table to store intermediate results.
Space Optimization (1D DP)	$O(m \times n)$	$O(n)$	Uses a 1D array for space optimization.

---

This approach ensures an efficient solution both in terms of time and space complexity. Let me know if you'd like further clarifications or examples!