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 (a 2D array) of the same size as the input grid. Initialize the top-left cell of the DP table with the value of the top-left cell in the grid.

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

3. Iterate and Update: Iterate through the remaining cells of the DP table. For each cell, its value will be the minimum of the sum of the cell above it and the cell to its left, plus the current cell's value in the grid.

4. Return the Bottom-Right Cell: The bottom-right cell of the DP table will contain the minimum path sum. Return this value.

Explanation

This solution uses dynamic programming. The DP table dp[i][j] stores the minimum path sum to reach cell (i, j). To reach (i, j), you must come from either (i-1, j) (above) or (i, j-1) (left). Therefore, the minimum path sum to reach (i, j) is the minimum of the minimum path sums to reach (i-1, j) and (i, j-1), plus the value of grid[i][j].

This approach avoids redundant calculations by storing and reusing previously computed minimum path sums. It efficiently finds the optimal solution in O(m*n) time.

Code

public 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];

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

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

        // Iterate and update
        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 bottom-right cell
        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), as we use a DP table of size m x n. We could potentially optimize this to O(min(m,n)) by only storing the previous row or column, but this solution prioritizes clarity.