Minimum sum path in the matrix, (count paths and similar type do, also backtrack to find the Minimum path)

Problem Overview

In this article, we'll explore the LeetCode problem "Minimum Path Sum," which involves finding the path with the smallest sum from the top-left to the bottom-right corner in a grid. The goal is to understand the problem deeply, explore the dynamic programming concepts that solve it, and analyze the solution's time and space complexities.

You can find the problem on LeetCode using this link.

Understanding the Problem

Given a grid filled with non-negative numbers, the task is to find a path from the top-left corner to the bottom-right corner of the grid, where each step can only move either down or right. The objective is to minimize the sum of the numbers on the path.

Problem Constraints

• The input grid is an m x n matrix.
• You can only move to the right or down at any point in time.

Example

Consider the grid below:

[
  [1, 3, 1],
  [1, 5, 1],
  [4, 2, 1]
]

The path with the minimum sum is 1 → 3 → 1 → 1 → 1, which equals 7.

Key DSA Concepts and Theory

Dynamic Programming

Dynamic programming (DP) is an optimization technique used to solve complex problems by breaking them down into simpler subproblems. It is applicable where the problem can be divided into overlapping subproblems with optimal substructure.

In the "Minimum Path Sum" problem, DP helps in storing and reusing the results of previously computed states, thus avoiding unnecessary recomputation, and making the solution efficient.

Key components of DP:

• Substructure: A problem has an optimal substructure if its optimal solution can be constructed from the optimal solutions of its subproblems.
• Overlapping Subproblems: A problem has overlapping subproblems if it can be broken down into subproblems which are reused several times.

Solution Approach

Step-by-Step Solution

1. Initialization: Create a 2D table dp of the same size as the grid to store the minimum path sum to reach each cell.
2. Base Case: Initialize dp[0][0] with grid[0][0] since there is no other path to reach the top-left corner.
3. First Row and First Column: Initialize the first row and first column independently because there is only one way to reach any cell in these locations (either only moving right for the first row or down for the first column).
4. DP Transition: For each cell grid[i][j] not in the first row or column, the minimum path sum to reach dp[i][j] is given by: [ \text{dp}[i][j] = \text{grid}[i][j] + \min(\text{dp}[i-1][j], \text{dp}[i][j-1]) ] This accounts for the cost of reaching a cell either from the top or from the left.
5. Return the Result: The result will be stored in dp[m-1][n-1], which is the minimum path sum to reach the bottom-right corner of the grid.

Implementation in C++

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int>> dp(m, vector<int>(n, 0));

        dp[0][0] = grid[0][0];

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

        // Fill the 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] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1]);
            }
        }

        return dp[m-1][n-1];
    }
};

Implementation in Java

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];
        
        dp[0][0] = grid[0][0];
        
        // Fill the first row
        for (int j = 1; j < n; j++) {
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        }
        
        // Fill the 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] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        
        return dp[m-1][n-1];
    }
}

Time and Space Complexity Analysis

Time Complexity:
The solution involves filling up an m x n table. Hence, the time complexity is O(m * n).

Space Complexity:
The space required for the DP table is O(m * n). However, this can be optimized to O(min(m, n)) by keeping only the current and previous rows (or columns) if only values from the previous states are required.

Common Mistakes to Avoid

• Ignoring Edge Cases: Always consider edge cases like a grid with only one row or column.
• Incorrect Indices Handling: Be cautious with indices while transitioning states in the DP table.
• Overlapping Subproblem Counting: Avoid recalculating values by ensuring that all intermediate results are stored and reused.

Similar Problems on LeetCode

1. LeetCode 62: Unique Paths
2. LeetCode 63: Unique Paths II
3. LeetCode 518: Coin Change 2
4. LeetCode 931: Minimum Falling Path Sum

Additional Resources and References

• "Introduction to Algorithms" by Cormen, Leiserson, Rivest, and Stein
• LeetCode’s Official Discuss Section for additional problem-specific discussions
• Dynamic Programming on Khan Academy

This comprehensive guide should equip you with a strong understanding of the "Minimum Path Sum" problem and its solution using dynamic programming.