Minimum Path Sum

Problem Statement

The task is to navigate a given m x n grid filled with non-negative integers and find the path from the top-left to the bottom-right corner which yields the minimum sum of the values along its path. The only movements allowed are either to the right or downward. This problem combines aspects of dynamic programming and path-finding in a grid-based system, and is well-suited for algorithms that effectively manage state space and decisions based on past values.

Examples

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

Constraints

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 200
• 0 <= grid[i][j] <= 200

Approach and Intuition

1. Follow the concepts of Dynamic Programming (DP), since optimal decisions at each cell depend on the decisions taken at previous steps.

2. Define a DP table, dp, where dp[i][j] will represent the minimum path sum to reach cell (i, j) from the top left corner (0, 0).

3. Initialize the top-left corner of the DP table, dp[0][0], with the value of grid[0][0] as that's the starting point.

4. For each cell (i, j), the minimum cost to get there can be calculated by considering the cost to get to the cell directly above it (i.e., from (i-1, j), moving down) and the cell directly to its left (i.e., from (i, j-1), moving right). Therefore, each cell dp[i][j] can be calculated as dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j].

5. The boundary rows and columns need special attention as they can only be reached from either directly above or directly from the left:

   • For the first row, where i = 0, dp[0][j] = dp[0][j-1] + grid[0][j] since we can only come from the left.
   • For the first column, where j = 0, dp[i][0] = dp[i-1][0] + grid[i][0] because the only approach is from above.

6. Continue filling up the DP table using the above rules until the bottom-right corner of the grid is processed. The value at dp[m-1][n-1] will then be the minimum path sum from the top-left to the bottom-right of the grid.

7. This approach leverages the overlapping subproblem property where the results of smaller problems are reused in larger ones, which is quintessential to dynamic programming.

The simplicity of the conditions (only move right or down) and the constraints (grid sizes and cell values) make a dynamic programming approach quite feasible and optimal for this kind of problem, ensuring it runs in polynomial time relative to the grid size.

Solutions

// C++ implementation
class Solution {
public:
    int calculateMinPath(vector<vector<int>>& matrix) {
        for (int row = matrix.size() - 1; row >= 0; --row) {
            for (int col = matrix[0].size() - 1; col >= 0; --col) {
                if (row == matrix.size() - 1 && col != matrix[0].size() - 1)
                    matrix[row][col] += matrix[row][col + 1];
                else if (col == matrix[0].size() - 1 && row != matrix.size() - 1)
                    matrix[row][col] += matrix[row + 1][col];
                else if (col != matrix[0].size() - 1 && row != matrix.size() - 1)
                    matrix[row][col] += min(matrix[row + 1][col], matrix[row][col + 1]);
            }
        }
        return matrix[0][0];
    }
};