#931

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Minimum Falling Path Sum

Minimum Falling Path Sum is a matrix dynamic programming problem where each cell depends on three reachable cells above it.

array dynamic programming matrix

Problem Statement

You are given an n x n integer matrix, and you need the smallest possible total from a falling path that starts somewhere in the first row and moves to the last row. On each step downward, you may stay in the same column, move one column left, or move one column right, so every choice is constrained by the row directly above.

This problem is about choosing locally valid downward moves while preserving the globally minimum sum. In [[2,1,3],[6,5,4],[7,8,9]], the best route totals 13, and negative values matter too, as in [[ -19,57],[-40,-5]], where the minimum path sum becomes -59 because the optimal transition keeps the most negative reachable chain.

Examples

Example 1

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

Output: 13

There are two falling paths with a minimum sum as shown.

Example 2

Input: matrix = [[-19,57],[-40,-5]]

Output: -59

The falling path with a minimum sum is shown.

Constraints

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

Solution Approach

Define the DP state by landing position

Let dp[row][col] represent the minimum falling path sum that ends at matrix[row][col]. The first row is the base case because any path may start there, so dp[0][col] = matrix[0][col]. This framing matches the exact rule of the problem: every later choice depends only on the three cells that could legally reach the current position.

Apply the three-way state transition carefully

For each cell in rows 1 through n - 1, look at up to three predecessors from the previous row: col - 1, col, and col + 1, as long as they stay inside bounds. Set dp[row][col] = matrix[row][col] + min(valid predecessors). The main failure mode here is boundary handling, because the leftmost and rightmost columns do not have all three incoming options.

Return the best path ending in the last row

Once every row is processed, any cell in the final row could be the end of the minimum falling path. Take the minimum value across that last row and return it. You can keep a full n x n table for clarity or compress to one previous-row array because each transition only needs the row above.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

A standard bottom-up DP visits each matrix cell once and checks at most three predecessors, so the time complexity is O(n^2). Space is O(n^2) with a full table, or O(n) if you keep only the previous row because Minimum Falling Path Sum never needs states older than one row back.

What Interviewers Usually Probe

They want a DP state that is tied to position, not path enumeration, because each move depends only on the previous row.
They are checking whether you spot the three-source transition and handle edge columns without branching bugs.
They may ask for space optimization after the full-table solution, since the matrix transition only needs one prior row.

Common Pitfalls or Variants

Common pitfalls

Using a greedy choice per row fails because the smallest immediate next value may block a better total path later.
Forgetting boundary checks at column 0 or n - 1 causes invalid predecessor access or incorrect minimums.
Mutating values in the wrong order during space optimization can mix current-row updates with previous-row states.

Follow-up variants

Return the maximum falling path sum instead of the minimum by flipping the transition aggregator from min to max.
Allow additional moves, such as two columns away, which changes the transition set but keeps the same row-based DP pattern.
Reconstruct the actual minimum path, not just the sum, by storing parent pointers alongside each DP state.

FAQ

What is the best pattern for Minimum Falling Path Sum?

The best pattern is state transition dynamic programming on a matrix. Each cell stores the minimum path sum ending there, using the three reachable cells from the previous row.

Why does greedy not work for this problem?

A locally small move can lead into large values later, while a slightly larger move now may open a much smaller total path below. Minimum Falling Path Sum needs full DP because the optimal substructure depends on cumulative sums, not per-step minimum choices.

Can I solve Minimum Falling Path Sum in place?

Yes, you can update the matrix row by row if modifying the input is allowed. Since each row only depends on the row above, in-place DP works as long as you never overwrite values that are still needed as predecessors.

What are the edge cases to watch in this matrix DP?

Single-cell matrices return that one value immediately, and negative numbers can make the minimum path strongly non-intuitive. The most common edge bug is mishandling the first and last columns, where only two predecessor positions may exist.

How do I reduce space in this state transition dynamic programming solution?

Keep only one array for the previous row and build a new array for the current row. After finishing the row, replace the previous array, which reduces extra space from O(n^2) to O(n) while preserving the same transition logic.

terminal

Solution

Solution 1

#### Python3

class Solution:
    def minFallingPathSum(self, matrix: List[List[int]]) -> int:
        n = len(matrix)
        f = [0] * n
        for row in matrix:
            g = [0] * n
            for j, x in enumerate(row):
                l, r = max(0, j - 1), min(n, j + 2)
                g[j] = min(f[l:r]) + x
            f = g
        return min(f)

Continue Practicing

#773 sliding puzzle #741 cherry pickup #1139 largest 1 bordered square