Problem 29.5 · DP on GridsMedium

Minimum Falling Path Sum

What it teaches: Three predecessors per cell (diagonals), with boundary checks.

Practise it on judges as “Minimum Falling Path Sum”.

The problem

In an n × n matrix, a falling path starts in any cell of the first row and moves to the row below at the same column or one column left or right. Return the minimum sum.

Example 1

Input: matrix = [[2,1,3],[6,5,4],[7,8,9]]
Output: 13

Constraints

1 ≤ n ≤ 100

Pattern clues in the wording

→ Row by row, three choices

These clues point to Grid DP: Each cell's answer comes from the cells above and to the left; fill the grid row by row.

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public int minFallingPathSum(int[][] matrix) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	matrix = [[2,1,3],[6,5,4],[7,8,9]]	13
2	matrix = [[-19,57],[-40,-5]]	-59

From slow to fast

Approaches

1. Row-by-row DP · O(n²)

Row-by-row DP

Time O(n²) Space O(n)

prev = first row; for each next row compute cur from prev with bounds checks; answer = min of the last row.

Approach 1

class Solution {
    public int minFallingPathSum(int[][] matrix) {
        int n = matrix.length;
        int[] prev = matrix[0].clone();
        for (int r = 1; r < n; r++) {
            int[] cur = new int[n];
            for (int c = 0; c < n; c++) {
                int best = prev[c];
                if (c > 0) best = Math.min(best, prev[c - 1]);
                if (c < n - 1) best = Math.min(best, prev[c + 1]);
                cur[c] = matrix[r][c] + best;
            }
            prev = cur;
        }
        int ans = Integer.MAX_VALUE;
        for (int x : prev) ans = Math.min(ans, x);
        return ans;
    }
}

Verdict: Straightforward.

Before you submit

Edge cases and common mistakes

Test these inputs

1 × 1
Negative values

Mistakes people make

Updating in place (a cell's new value would be read by its right neighbour as "above").

Interview

Follow-up questions

What if consecutive rows must use different columns (Falling Path Sum II)?

Command Palette

The problem

Approaches

Row-by-row DP

Edge cases and common mistakes

Follow-up questions