☕ DSA Java Articles

Topics › Dynamic Programming › 2D/3D DP and DP on Grids

Minimum sum path in the matrix

Medium TUF ID 2797 SDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given an m × n grid of non-negative integers. Start at the top-left cell (0, 0) and walk to the bottom-right cell (m - 1, n - 1). From any cell you may move only right or down. The cost of a path is the sum of every cell it visits, including both corners. Return the minimum possible cost.

Constraints (LeetCode 64): 1 ≤ m, n ≤ 200, 0 ≤ grid[i][j] ≤ 200. The largest possible path sum is 399 × 200 = 79,800, so int is enough.

Example 1

grid = [[1, 3, 1],
        [1, 5, 1],
        [4, 2, 1]]
answer = 7          // 1 → 3 → 1 → 1 → 1 (right, right, down, down)

Example 2

grid = [[1, 2, 3],
        [4, 5, 6]]
answer = 12         // 1 → 2 → 3 → 6

Why greedy fails and DP works

A tempting idea is to step to whichever neighbour (right or down) is cheaper. In Example 1 that happens to work, but take [[1, 1, 100], [2, 100, 100], [1, 1, 1]]. Greedy prefers the 1 on the right over the 2 below, and from there every route crosses at least one 100, so it ends at 104 or more. Going down first, 1 → 2 → 1 → 1 → 1, costs only 6. A cheap step now can lock you into an expensive future.

What does hold is this: every path that reaches (i, j) arrives either from (i - 1, j) (above) or from (i, j - 1) (left). Whatever happens after (i, j) does not depend on how we got there. So the cheapest way to reach (i, j) is grid[i][j] plus the cheaper of the cheapest ways to reach those two neighbours:

f(0, 0) = grid[0][0]
f(i, j) = grid[i][j] + min( f(i - 1, j), f(i, j - 1) )     with f = ∞ outside the grid
answer  = f(m - 1, n - 1)

That is optimal substructure (the best path to a cell extends a best path to a neighbour) and overlapping subproblems (both (i + 1, j) and (i, j + 1) ask for f(i, j)). Those two properties are exactly what dynamic programming needs.

Approach 1: Recursion

Intuition. Translate the recurrence directly. Start from the target and ask “where could I have come from?” Cells outside the grid return Integer.MAX_VALUE so that min never picks them. Because at least one of the two neighbours is always inside the grid when (i, j) ≠ (0, 0), we never add a cell to MAX_VALUE, so there is no overflow.

Algorithm.

  1. If (i, j) is (0, 0), return grid[0][0].
  2. If i < 0 or j < 0, return infinity.
  3. Return grid[i][j] + min(solve(i - 1, j), solve(i, j - 1)).
static int recursion(int[][] grid) {
    return solve(grid.length - 1, grid[0].length - 1, grid);
}

static int solve(int i, int j, int[][] grid) {
    if (i == 0 && j == 0) return grid[0][0];
    if (i < 0 || j < 0) return Integer.MAX_VALUE;        // off the grid: never the cheaper option
    int fromUp = solve(i - 1, j, grid);
    int fromLeft = solve(i, j - 1, grid);
    return grid[i][j] + Math.min(fromUp, fromLeft);
}

Complexity. Time O(2^(m+n)): every call branches twice and the depth is m + n - 2. Space O(m + n) for the recursion stack.

The same cell is recomputed many times. solve(1, 1) is reached from both solve(2, 1) and solve(1, 2), and each of those is reached from two more, and so on.

Approach 2: Memoization

Intuition. There are only m × n distinct states, so store each answer the first time it is computed. Because all values are non-negative, every real answer is ≥ 0, so -1 is a safe “not computed yet” marker.

Algorithm.

  1. Create dp[m][n] filled with -1.
  2. Same recursion as before, but return dp[i][j] if it is already filled, and save the result before returning.
static int memoization(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int[][] dp = new int[m][n];
    for (int[] row : dp) Arrays.fill(row, -1);
    return memo(m - 1, n - 1, grid, dp);
}

static int memo(int i, int j, int[][] grid, int[][] dp) {
    if (i == 0 && j == 0) return grid[0][0];
    if (i < 0 || j < 0) return Integer.MAX_VALUE;
    if (dp[i][j] != -1) return dp[i][j];
    int fromUp = memo(i - 1, j, grid, dp);
    int fromLeft = memo(i, j - 1, grid, dp);
    return dp[i][j] = grid[i][j] + Math.min(fromUp, fromLeft);
}

Complexity. Time O(m × n): each state is solved once with O(1) work. Space O(m × n) for the table plus O(m + n) stack.

Approach 3: Tabulation

Intuition. Reverse the direction. f(i, j) depends only on the cell above and the cell to the left, so if we fill the table row by row, left to right, both are ready when we need them. This removes the recursion stack entirely. The first row and first column are special: the first row can only be entered from the left, the first column only from above.

Algorithm.

  1. dp[0][0] = grid[0][0].
  2. For each cell in row-major order:
    • first row: dp[0][j] = grid[0][j] + dp[0][j - 1];
    • first column: dp[i][0] = grid[i][0] + dp[i - 1][0];
    • otherwise: dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1]).
  3. Return dp[m - 1][n - 1].
static int tabulation(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int[][] dp = new int[m][n];                            // dp[i][j]: cheapest path sum from (0,0) to (i,j)
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (i == 0 && j == 0) dp[i][j] = grid[0][0];
            else if (i == 0) dp[i][j] = grid[i][j] + dp[i][j - 1];     // first row: only from the left
            else if (j == 0) dp[i][j] = grid[i][j] + dp[i - 1][j];     // first column: only from above
            else dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return dp[m - 1][n - 1];
}

Dry run on Example 1 (each entry is dp[i][j]):

  j = 0 j = 1 j = 2
i = 0 1 1 + 3 = 4 4 + 1 = 5
i = 1 1 + 1 = 2 5 + min(4, 2) = 7 1 + min(5, 7) = 6
i = 2 2 + 4 = 6 2 + min(7, 6) = 8 1 + min(6, 8) = 7

Complexity. Time O(m × n). Space O(m × n).

Approach 4: Space optimised

Intuition. Row i only reads row i - 1. We can go further than keeping two rows: keep one array row of length n. When we are about to overwrite row[j] for row i, it still holds the value for (i - 1, j) (the cell above), and row[j - 1] has already been overwritten with the value for (i, j - 1) (the cell to the left). Those are exactly the two values the recurrence needs.

Algorithm.

  1. Allocate row[n].
  2. For each row i, for each column j from left to right, apply the same three cases as tabulation, reading row[j] as “above” and row[j - 1] as “left”.
  3. Return row[n - 1].
static int spaceOptimised(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int[] row = new int[n];                                // before the update row[j] is the cell above
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (i == 0 && j == 0) row[j] = grid[0][0];
            else if (i == 0) row[j] = grid[i][j] + row[j - 1];
            else if (j == 0) row[j] = grid[i][j] + row[j];
            else row[j] = grid[i][j] + Math.min(row[j], row[j - 1]);
        }
    }
    return row[n - 1];
}

Complexity. Time O(m × n). Space O(n). If m is much smaller than n, iterate column by column instead to get O(min(m, n)).

Edge cases and pitfalls