14.7 Minimum Path Sum

14.7.1 Problem Metadata

14.7.2 Description

Given a grid of non-negative numbers, move only right or down from the top-left cell to the bottom-right, minimizing the sum of values along the path.

14.7.3 Examples

Input: [[1,3,1],[1,5,1],[4,2,1]]
Output: 7

14.7.4 Constraints

  • 1 <= m, n <= 200

14.7.5 Solution - DP Table

14.7.5.1 Walkthrough

Set dp[i][j] to the minimum sum needed to reach (i, j). Initialize the first row and column with cumulative sums. For each other cell, add the current value to the minimum of the top or left neighbor.

14.7.5.2 Analysis

  • Time Complexity: O(m * n)
  • Space Complexity: O(m * n) (can be optimized to O(n))

14.7.5.3 Implementation Steps

  1. Initialize dp[0][0] = grid[0][0].
  2. Fill the first row/column cumulatively.
  3. For i > 0, j > 0, set dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]).
  4. Return dp[m-1][n-1].

14.7.5.4 Code - Java

public int minPathSum(int[][] grid) {
    int rows = grid.length;
    int cols = grid[0].length;
    int[][] dp = new int[rows][cols];

    dp[0][0] = grid[0][0];
    for (int c = 1; c < cols; c++) {
        dp[0][c] = dp[0][c - 1] + grid[0][c];
    }
    for (int r = 1; r < rows; r++) {
        dp[r][0] = dp[r - 1][0] + grid[r][0];
    }

    for (int r = 1; r < rows; r++) {
        for (int c = 1; c < cols; c++) {
            dp[r][c] = grid[r][c] + Math.min(dp[r - 1][c], dp[r][c - 1]);
        }
    }

    return dp[rows - 1][cols - 1];
}