Minimum Path Sum medium

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 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

Steps

1. Initialization: Create a DP table (2D array) of the same size as the grid. Initialize the top-left cell of the DP table with the value of the top-left cell in the grid.

2. First Row and First Column: Fill the first row and the first column of the DP table. For the first row, each cell's value is the sum of the values of the cells to its left in the grid. Similarly, for the first column, each cell's value is the sum of the values of the cells above it in the grid.

3. Iteration: Iterate through the rest of the DP table. For each cell dp[i][j], its value represents the minimum path sum to reach that cell. This minimum sum is the smaller of two possibilities:

   • The minimum path sum to reach the cell from the cell above (dp[i-1][j]) plus the current cell's value in the grid.
   • The minimum path sum to reach the cell from the cell to the left (dp[i][j-1]) plus the current cell's value in the grid.

4. Result: The bottom-right cell of the DP table (dp[m-1][n-1]) contains the minimum path sum from the top-left to the bottom-right cell.

Explanation

This problem is a classic dynamic programming problem. The key idea is that the minimum path sum to reach a cell is dependent only on the minimum path sums to the cells above and to the left of it. By building up the solution from the top-left to the bottom-right, we can efficiently compute the minimum path sum. The DP table stores the minimum path sums for each cell, avoiding redundant calculations.

Code

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        // Create DP table
        int[][] dp = new int[m][n];

        // Initialize top-left cell
        dp[0][0] = grid[0][0];

        // Initialize first row
        for (int i = 1; i < n; i++) {
            dp[0][i] = dp[0][i - 1] + grid[0][i];
        }

        // Initialize first column
        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }

        // Iterate through 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];
            }
        }

        // Return the minimum path sum
        return dp[m - 1][n - 1];
    }
}

Complexity

• Time Complexity: O(m*n), where 'm' and 'n' are the dimensions of the grid. We iterate through the DP table once.
• Space Complexity: O(m*n), due to the DP table. We can optimize this to O(min(m,n)) by using a 1D array if needed, but this would make the code slightly less readable.