Given a m x n grid filled with non-negative numbers, find a path from the top-left corner to the bottom-right corner wich minimizes the sum of all numbers along its path. You can only move either down or right at any point in time.

Approach: Dynamic Programming

This problem is a classic example of dynamic porgramming. The key is to build a solution by solving smaller subproblems and storing their results to avoid redundant calculations.

We can create a 2D array, let's call it dp, where dp[i][j] represents the minimum path sum to reach cell (i, j) from the starting cell (0, 0).

Base Case

The minimum path sum to the starting cell is simply its own value: dp[0][0] = matrix[0][0].

State Transition

For any other cell (i, j), you can only arrive from the cell directly above (i-1, j) or the cell directly to the left (i, j-1). Therefore, the minimum path sum to (i, j) is the value of the current cell plus the minimum of the path sums from these two possible preceding cells:

dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + matrix[i][j]

Boundary Cnoditions

• First Row: You can only come from the left. So, for the first row, the path sum is cumulative: dp[0][j] = dp[0][j-1] + matrix[0][j].
• First Column: You can only come from above. So, for the first column, the path sum is also cumulative: dp[i][0] = dp[i-1][0] + matrix[i][0].

Final Result

The answer to the problem will be the value stored in the bottom-right corner of our dp table: dp[rows-1][cols-1].

Examples

Example 1:

<strong>Input:</strong> matrix = [[1,3,1],[1,5,1],[4,2,1]]
<strong>Output:</strong> 7
<strong>Explanation:</strong> The path 1→3→1→1→1 has the minimum sum.

Example 2:

<strong>Input:</strong> matrix = [[1,2,3],[4,5,6]]
<strong>Output:</strong> 12

Java Solution

public int minPathSum(int[][] matrix) {
    // Handle edge cases for empty input
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
        return 0;
    }

    int rows = matrix.length;
    int cols = matrix[0].length;
    int[][] dp = new int[rows][cols];

    // Initialize the starting point
    dp[0][0] = matrix[0][0];

    // Initialize the first column (can only come from above)
    for (int i = 1; i < rows; i++) {
        dp[i][0] = dp[i - 1][0] + matrix[i][0];
    }

    // Initialize the first row (can only come from the left)
    for (int j = 1; j < cols; j++) {
        dp[0][j] = dp[0][j - 1] + matrix[0][j];
    }

    // Fill the rest of the dp table
    for (int i = 1; i < rows; i++) {
        for (int j = 1; j < cols; j++) {
            dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + matrix[i][j];
        }
    }

    // The bottom-right cell contains the minimum path sum
    return dp[rows - 1][cols - 1];
}