☕ DSA Java Articles

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

Minimum Falling Path Sum

Medium TUF ID 298 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Given a matrix of integers, a falling path starts at any cell of the first row and moves down one row at a time. From cell (i, j) the next cell is (i + 1, j - 1), (i + 1, j) or (i + 1, j + 1): down-left, straight down or down-right, staying inside the matrix. It ends at some cell of the last row. Return the minimum possible sum of the values along a falling path.

This is LeetCode 931, where the matrix is n × n with 1 ≤ n ≤ 100 and values in [-100, 100]. The Java methods work on any rectangular n × m matrix. Striver’s lecture on this pattern asks for the maximum falling path sum on a rectangular matrix; swapping every min for max (and the infinity for minus infinity) gives that version.

Example 1

matrix = [[2, 1, 3],
          [6, 5, 4],
          [7, 8, 9]]
answer = 13         // 1 -> 5 -> 7, or 1 -> 4 -> 8

Example 2

matrix = [[-19, 57],
          [-40, -5]]
answer = -59        // -19 -> -40

What is new here

In Unique Paths the start and the end were fixed cells. Here both are variable: the path may start at any cell of row 0 and end at any cell of the last row. The standard way to handle this is to fix one end inside the recursion and loop over the other outside it. We define the state as “the path ends at (i, j)”, recurse upward to the first row, where any cell is a valid start (so that is the base case), and take the best over all cells of the last row.

Approach 1: Recursion

Intuition. Let f(i, j) be the minimum sum of a falling path that starts anywhere in row 0 and ends at (i, j). The step into (i, j) came from one of (i - 1, j - 1), (i - 1, j) or (i - 1, j + 1). Whichever it was, the part of the path above should be the cheapest path to that cell. So

f(i, j) = +infinity                                   if j is outside the matrix
f(0, j) = matrix[0][j]
f(i, j) = matrix[i][j] + min( f(i-1, j-1), f(i-1, j), f(i-1, j+1) )
answer  = min over j of f(n - 1, j)

“Infinity” here is 10^9, a value no real path sum can reach (the largest real magnitude is 100 · 100 = 10^4). It is only ever passed to min, and the straight-up neighbour is always inside the matrix, so infinity never wins and is never added to.

Algorithm.

  1. If j is out of range, return infinity.
  2. If i == 0, return matrix[0][j].
  3. Return matrix[i][j] plus the minimum of the three upward neighbours.
  4. The answer is the minimum of f(n - 1, j) over all columns j.
static int recursive(int[][] matrix) {
    int n = matrix.length, m = matrix[0].length;
    int best = Integer.MAX_VALUE;
    for (int j = 0; j < m; j++) best = Math.min(best, solve(n - 1, j, matrix));
    return best;
}

static int solve(int i, int j, int[][] matrix) {
    if (j < 0 || j >= matrix[0].length) return INF;         // stepped off the side
    if (i == 0) return matrix[0][j];                        // a path may start at any cell of row 0
    int up = solve(i - 1, j, matrix);
    int upLeft = solve(i - 1, j - 1, matrix);
    int upRight = solve(i - 1, j + 1, matrix);
    return matrix[i][j] + Math.min(up, Math.min(upLeft, upRight));
}

Complexity. Time O(m · 3^n): each of the m end cells starts a recursion that branches three ways for n - 1 levels. Space O(n) for the recursion depth.

Approach 2: Memoization

Intuition. There are n · m states, and neighbouring end cells share almost all of their upward recursion. Cache f(i, j) in dp[i][j].

Values can be negative, so -1 is no longer a safe “not computed” marker: a real path sum can be -1. The table is filled with Integer.MAX_VALUE instead, which no real sum can equal.

Algorithm.

  1. Create dp[n][m] filled with Integer.MAX_VALUE.
  2. In the helper, apply the two base cases, then return dp[i][j] if it was computed; otherwise compute, store and return it.
  3. Take the minimum over the last row as before. The table is shared across the m starting calls, which is what makes the total work O(n · m).
static int memoization(int[][] matrix) {
    int n = matrix.length, m = matrix[0].length;
    int[][] dp = new int[n][m];
    for (int[] row : dp) Arrays.fill(row, Integer.MAX_VALUE);   // MAX_VALUE = not computed (sums can be negative)
    int best = Integer.MAX_VALUE;
    for (int j = 0; j < m; j++) best = Math.min(best, memo(n - 1, j, matrix, dp));
    return best;
}

static int memo(int i, int j, int[][] matrix, int[][] dp) {
    if (j < 0 || j >= matrix[0].length) return INF;
    if (i == 0) return matrix[0][j];
    if (dp[i][j] != Integer.MAX_VALUE) return dp[i][j];
    int up = memo(i - 1, j, matrix, dp);
    int upLeft = memo(i - 1, j - 1, matrix, dp);
    int upRight = memo(i - 1, j + 1, matrix, dp);
    return dp[i][j] = matrix[i][j] + Math.min(up, Math.min(upLeft, upRight));
}

Complexity. Time O(n · m): each cell is computed once with three lookups. Space O(n · m) plus O(n) stack.

Approach 3: Tabulation

Intuition. Row i only reads row i - 1, so fill the table from the top down. Row 0 is the base case, copied from the matrix. Out-of-range neighbours are replaced by infinity, just as in the recursion.

Algorithm.

  1. dp[0][j] = matrix[0][j] for all j.
  2. For each row i ≥ 1 and column j: dp[i][j] = matrix[i][j] + min(dp[i-1][j], dp[i-1][j-1] if j > 0, dp[i-1][j+1] if j < m - 1).
  3. Return the minimum of the last row.
static int tabulation(int[][] matrix) {
    int n = matrix.length, m = matrix[0].length;
    int[][] dp = new int[n][m];
    for (int j = 0; j < m; j++) dp[0][j] = matrix[0][j];
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int up = dp[i - 1][j];
            int upLeft = j > 0 ? dp[i - 1][j - 1] : INF;
            int upRight = j < m - 1 ? dp[i - 1][j + 1] : INF;
            dp[i][j] = matrix[i][j] + Math.min(up, Math.min(upLeft, upRight));
        }
    }
    int best = Integer.MAX_VALUE;
    for (int j = 0; j < m; j++) best = Math.min(best, dp[n - 1][j]);
    return best;
}

Dry run on Example 1:

row j = 0 j = 1 j = 2
0 2 1 3
1 6 + min(2, 1) = 7 5 + min(2, 1, 3) = 6 4 + min(1, 3) = 5
2 7 + min(7, 6) = 13 8 + min(7, 6, 5) = 13 9 + min(6, 5) = 14

The minimum of the last row is 13.

Complexity. Time O(n · m), space O(n · m).

Approach 4: Space optimized

Intuition. Only the previous row is ever read. Keep it in prev, build the new row in cur, and swap. Unlike Unique Paths, a single in-place array does not work here: cur[j] needs the old prev[j - 1], which an in-place left-to-right update would already have overwritten. Two arrays avoid the problem.

Algorithm.

  1. prev = copy of matrix[0].
  2. For each later row, compute cur[j] from prev[j - 1], prev[j], prev[j + 1], then prev = cur.
  3. Return the minimum of prev.
static int spaceOptimized(int[][] matrix) {
    int n = matrix.length, m = matrix[0].length;
    int[] prev = matrix[0].clone();
    for (int i = 1; i < n; i++) {
        int[] cur = new int[m];
        for (int j = 0; j < m; j++) {
            int up = prev[j];
            int upLeft = j > 0 ? prev[j - 1] : INF;
            int upRight = j < m - 1 ? prev[j + 1] : INF;
            cur[j] = matrix[i][j] + Math.min(up, Math.min(upLeft, upRight));
        }
        prev = cur;
    }
    int best = Integer.MAX_VALUE;
    for (int v : prev) best = Math.min(best, v);
    return best;
}

Complexity. Time O(n · m), space O(m).

Edge cases and pitfalls