How do you approach Minimum Falling Path Sum?

Row by row, the best path into a cell comes from the three cells above it.

What are common mistakes on Minimum Falling Path Sum?

Iterating the dimensions in an order that reads a cell before it has been written. Getting the base case wrong. It carries the whole recurrence, and the error stays invisible until a large input. Rolling down to one dimension without reversing the inner loop, which lets a 0/1 item be taken twice.

← Back to problems

Minimum Falling Path Sum

MediumAlgorithms

Description

Given an `n x n` integer `matrix`, return the minimum sum of any **falling path**. A falling path starts at any cell in the first row and chooses the cell directly below or diagonally below-left/right at each step (column changes by at most 1).

Example 1

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

Output: 13

Explanation: 1 -> 5 -> 7 gives 13.

Constraints

- n == matrix.length == matrix[i].length - 1 <= n <= 100 - -100 <= matrix[i][j] <= 100

Minimum Falling Path Sum: approach, complexity and pitfalls

A medium dynamic programming problem, graded against 4 test cases (2 of them hidden).

The pattern: Dynamic Programming

Overlapping subproblems solved once and reused - the pattern candidates fear most.

Reach for it when you see: "Number of ways", "minimum/maximum cost", or a recursion that recomputes the same state.

More Dynamic Programmingproblems →

If you are stuck

Show the 2-step hint ladder

Row by row, the best path into a cell comes from the three cells above it.
Keep a rolling array of the best sums for the previous row.

The optimal approach

Show the approach: The approach

Row-by-row DP. `dp[j]` holds the minimum falling-path sum ending at column `j` of the current row, computed from the previous row's `dp[j-1]`, `dp[j]`, and `dp[j+1]`. The answer is the minimum over the last row.

Time: O(n²). Space: O(n).

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Negative numbers. The suite includes negative values. Running-sum, min/max seeding and any "initialise to zero" step need to handle them.

Common Dynamic Programming mistakes

These apply to the pattern as a whole, not just this problem.

Iterating the dimensions in an order that reads a cell before it has been written.
Getting the base case wrong. It carries the whole recurrence, and the error stays invisible until a large input.
Rolling down to one dimension without reversing the inner loop, which lets a 0/1 item be taken twice.