Minimum Falling Path Sum: Matrix Dynamic Programming

LeetCode Minimum Falling Path Sum (problem 931) asks you to find the smallest sum you can get by choosing one element from each row, where each choice must be directly below or diagonally adjacent to the previous one. Given an n x n matrix of integers, return the minimum sum of any falling path through the matrix. A falling path starts at any element in the first row and, at each step, moves to the cell directly below, below-left, or below-right.

Why this problem matters

This problem is a clean introduction to row-by-row dynamic programming on a 2D grid. Unlike path problems that restrict movement to only right and down, here you have three downward choices at each cell. The same pattern shows up in triangle problems, paint house problems, and many grid optimization tasks. Once you internalize this "propagate the best from above" technique, you can apply it to a wide family of matrix DP problems.

The brute force approach

The naive solution tries every possible falling path using recursion. From each cell in the first row, you branch into three choices in the next row, and so on until you reach the bottom.

def minFallingPathSum(matrix):
    n = len(matrix)

    def dfs(row, col):
        if row == n:
            return 0
        best = float('inf')
        for dc in [-1, 0, 1]:
            nc = col + dc
            if 0 <= nc < n:
                best = min(best, matrix[row][col] + dfs(row + 1, nc))
        return best

    return min(dfs(0, col) for col in range(n))

This explores up to 3^n paths, which is far too slow for any meaningful input size. Many subproblems overlap (reaching the same cell from different starting points), which is a strong signal that dynamic programming will help.

The key insight

Each cell's minimum falling path sum equals its own value plus the minimum of the three cells above it (directly above, above-left, above-right). You do not need to track the full path. You only need the best cost to reach each cell in the previous row. Build your DP table one row at a time, and at the end, the answer is the minimum value in the last row.

Walking through it step by step

The optimized solution

def minFallingPathSum(matrix):
    n = len(matrix)
    for i in range(1, n):
        for j in range(n):
            above = matrix[i - 1][j]
            above_left = matrix[i - 1][j - 1] if j > 0 else float('inf')
            above_right = matrix[i - 1][j + 1] if j < n - 1 else float('inf')
            matrix[i][j] += min(above, above_left, above_right)
    return min(matrix[-1])

Here is how it works:

1. Start from row 1 (the second row). Row 0 needs no updates because there is nothing above it.
2. For each cell (i, j), look at the three cells above: (i-1, j-1), (i-1, j), and (i-1, j+1). Treat out-of-bounds indices as infinity.
3. Add the minimum of those three values to matrix[i][j]. Now matrix[i][j] holds the minimum falling path sum ending at that cell.
4. After processing all rows, the answer is the minimum value in the last row.

Complexity analysis

Each cell is visited exactly once, and the work per cell is constant (comparing three neighbors). The in-place approach reuses the input matrix, so no extra allocation is needed.

Building blocks

1. Row-by-row DP propagation

The core pattern is processing a grid one row at a time, where each cell depends only on values from the row immediately above. This skeleton applies to many matrix DP problems:

for i in range(1, n):
    for j in range(n):
        # Combine matrix[i][j] with best values from row i-1
        matrix[i][j] += best_from_above(i, j)

The "best from above" function changes by problem: sometimes it is a minimum, sometimes a maximum, sometimes a count. The structure stays the same.

2. Boundary handling

Cells at the edges of the matrix have fewer than three predecessors. The left column has no above-left neighbor, and the right column has no above-right neighbor. Handle this with conditional checks or by treating out-of-bounds as infinity (for minimization problems) or zero (for counting problems):

above_left = matrix[i-1][j-1] if j > 0 else float('inf')
above_right = matrix[i-1][j+1] if j < n - 1 else float('inf')

This pattern keeps the inner loop clean and avoids special-casing the first and last columns.

Edge cases

• 1x1 matrix: The answer is just the single element. No falling path computation needed.
• All negative values: The algorithm still works correctly because you are always adding the minimum, and min of negatives is the most negative.
• All identical values: Every path has the same sum (n times the repeated value). The algorithm handles this naturally.
• Single column (n x 1 matrix): Each cell has exactly one predecessor (directly above). The falling path is forced, and the sum is the total of all elements in the column.

From understanding to recall

Understanding the "accumulate from above" pattern is the first step. The harder part is recognizing when to apply it during an interview. Matrix DP problems often disguise themselves: they might talk about paths, costs, or sequences on a grid, but the underlying structure is always "each cell depends on a small window of cells from the previous row."

Spaced repetition helps you build that recognition reflex. When you revisit this problem a few days later, you will not need to rederive the solution. Instead, you will immediately see "row-by-row DP with three predecessors" and write the code in minutes. That is the difference between understanding a solution and owning it.

The more matrix DP variants you practice (triangle, paint house, minimum path sum, dungeon game), the stronger your pattern library becomes. Each new problem reinforces the shared structure and sharpens your ability to spot it under time pressure.

Related posts

• Minimum Path Sum - Grid DP with restricted movement (right and down only)
• Triangle - Similar falling path concept on a triangular grid
• Unique Paths - Matrix DP where you count paths instead of minimizing sums

If you want to move from "I can solve this with hints" to "I can solve this cold in an interview," structured repetition is the fastest path. CodeBricks schedules review sessions that target exactly the problems you are about to forget, keeping your pattern recognition sharp without wasting time on problems you already own.