MediumArrayDynamic ProgrammingMatrix

Minimum Falling Path Sum

1 approach, code in every language

You are given a square integer grid. A falling path chooses exactly one number from every row, moving downward one row at a time.

When you drop from a cell in one row to the next row, the column can shift by at most one position: you may stay in the same column, move one column to the left, or move one column to the right. In other words, from column c you can land on column c - 1, c, or c + 1 in the row below (staying inside the grid).

Return the smallest possible sum obtainable by adding up the values along any single falling path.

Example 1

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

Output: 13

One optimal path is 1 -> 5 -> 7 (sum 13). Another path 1 -> 4 -> 8 also totals 13; no path does better.

Example 2

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

Output: -59

Choosing -19 from the top row and -40 from the bottom row (adjacent columns) gives the minimum sum -59.

Constraints

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

Bottom-Up DP over Rows

Sweep the grid row by row, tracking the best falling-path sum that ends at each column.

Loading animation…

Intuition

The minimum sum to reach a cell only depends on the three cells immediately above it: the one directly above and its two diagonal neighbors. That gives an optimal-substructure recurrence where each cell stores the smallest path total that ends there. We build these totals from the first row downward, so by the time we process row i we already know every optimal answer for row i - 1. Since a cell only reads the previous row, we can keep just one rolling array of size n. The final answer is the minimum value across the last row, because a path may end at any column.

Algorithm walkthrough

1Initialize the rolling array dp to a copy of the first row; dp[j] is the best path sum ending at column j.
2For each subsequent row i, snapshot the previous row's totals as prev before overwriting.
3For each column j, take best = min(prev[j], prev[j-1], prev[j+1]) while skipping neighbors that fall outside the grid.
4Set dp[j] = matrix[i][j] + best, folding the current cell's value into the cheapest arrival.
5After the last row is processed, return the minimum entry of dp as the overall answer.

Implementation

class Solution:
    def minFallingPathSum(self, matrix: List[List[int]]) -> int:
        n = len(matrix)
        dp = matrix[0][:]
        for i in range(1, n):
            prev = dp[:]
            for j in range(n):
                best = prev[j]
                if j > 0:
                    best = min(best, prev[j - 1])
                if j < n - 1:
                    best = min(best, prev[j + 1])
                dp[j] = matrix[i][j] + best
        return min(dp)

Time

O(n^2)

Space

O(n)

Every one of the n^2 cells is relaxed once against at most three neighbors; a single rolling row of size n replaces the full DP table.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Dynamic Programming

After the pattern

Now solve one you haven't seen.

Least Strain Down the Wall is our own problem on the technique behind Minimum Falling Path Sum: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free