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.

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

Steps

1. Initialization: Create a DP table (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. First Row and First Column: Fill the first row and first column of the DP table. Each cell's value represents the minimum sum to reach that cell from the top-left. This involves only moving right or down.

3. Iterative Filling: Iterate through the rest of the DP table. For each cell (i, j), the minimum path sum to reach this cell is the minimum of:

   • The minimum path sum to reach the cell above (i-1, j) plus the current cell's value.
   • The minimum path sum to reach the cell to the left (i, j-1) plus the current cell's value.

4. Result: The bottom-right cell of the DP table contains the minimum path sum from the top-left to the bottom-right.

Explanation

The dynamic programming approach efficiently solves this problem by breaking it down into smaller overlapping subproblems. Instead of exploring all possible paths (which would be computationally expensive), we build up the solution incrementally. Each cell in the DP table stores the optimal solution to reach that specific cell. By building up the table row by row or column by column, we avoid redundant calculations.

Code

#include <vector>
#include <limits> // for numeric_limits

using namespace std;

int minPathSum(vector<vector<int>>& grid) {
    int m = grid.size();
    int n = grid[0].size();

    // Create DP table and initialize
    vector<vector<int>> dp(m, vector<int>(n));
    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];
    }

    // Fill the rest of the DP table
    for (int i = 1; i < m; ++i) {
        for (int j = 1; j < n; ++j) {
            dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
        }
    }

    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), The space used by the DP table. We could optimize this to O(min(m,n)) by using only one row or column if needed.