AlgoMaster Logo

Minimum Falling Path Sum

mediumFrequencyUpdated September 21, 2026

Understanding the Problem

We have a square grid of numbers, and we need to find a path from the top row to the bottom row that has the smallest possible sum. The movement rule constrains the choices: from any cell, you can only move to the cell directly below, diagonally below-left, or diagonally below-right. At each row, that gives up to three choices for where to step next.

This is a dynamic programming problem. The minimum falling path ending at any cell in row i depends only on the minimum falling paths ending at the neighboring cells in row i - 1. There is optimal substructure (the best path to a cell builds on the best path to cells above it) and overlapping subproblems (multiple paths converge on the same cell).

We do not need to track the full path. For each cell, we only need the minimum cost to reach it from any cell in the first row.

Key Constraints:

  • 1 <= n <= 100 → At most 10,000 cells, so an O(n^2) solution is well within limits. The path sum stays within int range (at most 100 cells times 100 each, so 10,000 in magnitude), so no overflow handling is needed.
  • -100 <= matrix[i][j] <= 100 → Values can be negative, which rules out a greedy approach. Always picking the smallest neighbor can miss the optimum, because a locally larger value can sit above two very negative cells and lead to a smaller total. Every path has to be evaluated through the recurrence.

Approach 1: Brute Force (Recursion)

Intuition

Try every possible falling path and return the one with the smallest sum. From each cell in the first row, recursively explore all three options in the next row (below-left, below, below-right), accumulating the sum along the way. Reaching the last row gives a complete path sum.

This is a depth-first search over all possible paths. For each of the n starting positions in the first row, the search branches into up to 3 choices per row, forming a tree of possibilities.

Algorithm

  1. For each cell in the first row, start a recursive search.
  2. At each cell (row, col), if we are at the last row, return matrix[row][col].
  3. Otherwise, recursively compute the minimum falling path sum from each of the three cells in the next row: (row+1, col-1), (row+1, col), and (row+1, col+1). Skip any that are out of bounds.
  4. Return matrix[row][col] plus the minimum of the recursive results.
  5. The answer is the minimum across all starting cells in the first row.

Example Walkthrough

1Start DFS from (0,1) with value 1
0
1
2
0
2
start
1
3
1
6
5
4
2
7
8
9
1/6

Code

The bottleneck is recomputing the same (row, col) subproblems repeatedly. The next approach caches each result the first time it is computed.

Approach 2: Top-Down DP (Memoization)

Intuition

The brute force recurrence is correct, but it recomputes the same cells many times. Caching the result of dfs(row, col) after the first computation lets every later call to the same (row, col) return immediately. This memoization turns the exponential solution into a polynomial one.

There are at most n * n unique (row, col) pairs, and each does O(1) work after looking up its children, so the total work drops from O(3^n) to O(n^2).

Algorithm

  1. Create a memoization table (2D array or hash map) initialized with a sentinel value.
  2. For each cell in the first row, call the memoized recursive function.
  3. In the recursive function, check if we have already computed the result for (row, col). If so, return the cached value.
  4. Otherwise, compute it the same way as brute force, store the result, and return it.
  5. The answer is the minimum across all starting cells in the first row.

Example Walkthrough

1Start: DFS from (0,1), memo is empty
0
1
2
0
2
start
1
3
1
6
5
4
2
7
8
9
1/5

Code

Memoization reaches O(n^2) time, which is optimal here. The next approach fills the same table iteratively, removing the recursion overhead.

Approach 3: Bottom-Up DP

Intuition

Build the table iteratively from the top row downward instead of recursing. Define dp[i][j] as the minimum falling path sum ending at cell (i, j). The first row of the DP table equals the first row of the matrix. For every subsequent row, each cell's value is its matrix value plus the minimum of the up-to-three cells directly above it.

Once the entire table is filled, the answer is the minimum value in the last row. This is the same recurrence as the memoized solution, computed in a different order. Filling it iteratively avoids recursion overhead and sets up the space optimization in the next approach.

Algorithm

  1. Create a 2D DP table of size n x n. Copy the first row of the matrix into the first row of the DP table.
  2. For each row from 1 to n-1, and for each column j in that row:
    • Look at dp[row-1][j-1], dp[row-1][j], and dp[row-1][j+1] (skipping out-of-bounds indices).
    • Set dp[row][j] = matrix[row][j] + min of those values.
  3. Return the minimum value in dp[n-1].

Example Walkthrough

1Row 0 (base case): copy first row → dp = [2, 1, 3]
0
1
2
0
2
1
3
1
6
5
4
2
7
8
9
1/9

Code

Computing row i only reads from row i-1, so the rows above i-1 are never used again. The next approach keeps only the previous row instead of the entire table, dropping space from O(n^2) to O(n).

Approach 4: Space-Optimized Bottom-Up DP

Intuition

Since each row of the DP table only depends on the immediately previous row, two 1D arrays suffice instead of a full 2D table: one holds the previous row's results and one holds the row being computed. After processing a row, the current row becomes the previous row for the next iteration. Writing into a separate curr array keeps prev intact while it is still being read, so the three lookups for each cell always see the previous row's final values.

This is the rolling-array optimization for grid DP, where each row depends only on the one above it.

Algorithm

  1. Initialize a prev array with the first row of the matrix.
  2. For each subsequent row, create a curr array.
  3. For each column j, set curr[j] = matrix[row][j] + min of the relevant entries in prev.
  4. After processing the row, set prev = curr.
  5. Return the minimum value in prev after all rows are processed.

Example Walkthrough

1Initialize prev = matrix[0] = [2, 1, 3]
0
2
1
1
2
3
1/6

Code