Minimum Path Sum in C++ (O(n * m) Time Complexity)

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:

Input:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.

Note:

Your algorithm should run in O(n * m) time and use O(n * m) extra space.

Understanding the Problem

The core challenge of this problem is to find the path from the top-left corner to the bottom-right corner of a grid that results in the minimum sum of the numbers along the path. The only allowed movements are to the right or downward. This problem is significant in various applications such as robotics, game development, and pathfinding algorithms.

Approach

To solve this problem, we can use dynamic programming. The idea is to create a 2D array (dp) where dp[i][j] represents the minimum path sum to reach cell (i, j). The value of dp[i][j] can be computed as the minimum of the path sums from the cell above (i-1, j) and the cell to the left (i, j-1), plus the value of the current cell grid[i][j].

Naive Solution

A naive solution would involve exploring all possible paths from the top-left to the bottom-right corner, which would be highly inefficient due to the exponential number of possible paths.

Optimized Solution

The optimized solution uses dynamic programming to store the results of subproblems and build up the solution iteratively. This approach ensures that each cell is computed only once, resulting in a time complexity of O(n * m).

Algorithm

Create a 2D array dp of the same size as the input grid.
Initialize dp[0][0] with grid[0][0] since this is the starting point.
Fill the first row and first column of dp since there is only one way to reach any cell in the first row or column (either from the left or from above).
For each cell (i, j) in the grid, compute dp[i][j] as the minimum of dp[i-1][j] and dp[i][j-1] plus grid[i][j].
The value at dp[m-1][n-1] will be the minimum path sum from the top-left to the bottom-right corner.

Code Implementation

#include <vector>
#include <algorithm>
using namespace std;

// Function to find the minimum path sum in a grid
int minPathSum(vector<vector<int>>& grid) {
    int m = grid.size();
    int n = grid[0].size();
    
    // Create a 2D dp array to store the minimum path sums
    vector<vector<int>> dp(m, vector<int>(n, 0));
    
    // Initialize the starting point
    dp[0][0] = grid[0][0];
    
    // Fill the first row
    for (int i = 1; i < n; ++i) {
        dp[0][i] = dp[0][i - 1] + grid[0][i];
    }
    
    // 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 array
    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];
        }
    }
    
    // The bottom-right corner contains the minimum path sum
    return dp[m - 1][n - 1];
}

Complexity Analysis

The time complexity of this approach is O(n * m) because we iterate through each cell of the grid once. The space complexity is also O(n * m) due to the additional 2D dp array used to store the minimum path sums.

Edge Cases

Some potential edge cases include:

Grid with only one cell: The minimum path sum is the value of that cell.
Grid with one row or one column: The path is straightforward, either all right or all down.

Testing

To test the solution comprehensively, consider the following test cases:

Simple 3x3 grid as given in the example.
Grid with all zeros.
Grid with increasing values.
Grid with random values.

Thinking and Problem-Solving Tips

When approaching such problems, it is crucial to break down the problem into smaller subproblems and think about how to build up the solution iteratively. Practice dynamic programming problems to develop a strong understanding of this technique.

Conclusion

Understanding and solving the minimum path sum problem using dynamic programming is a valuable skill. It helps in developing problem-solving skills and understanding how to optimize solutions for efficiency. Practice similar problems to strengthen your grasp of dynamic programming.