DSA Tracker

Visualize

Minimum Falling Path Sum

dp[r][c] = matrix[r][c] + min(dp[r-1][c-1], dp[r-1][c], dp[r-1][c+1])

time O(n^2)space O(1) extra (in place)

A falling path through row r can only have arrived from three cells in row r-1: the one directly above, and its two diagonal neighbors — nothing else is reachable in one step down. So the cheapest way to reach any cell is the cheapest way to reach one of those three, plus the cell's own value. Filling the matrix top to bottom with that rule turns every cell into 'the minimum falling path sum ending here', and once the last row is filled, its smallest value IS the answer — no need to ever list an actual path.

Details

Animated on: matrix = [[2,1,3],[6,5,4],[7,8,9]] — a falling path picks one cell per row, moving to the cell directly below or diagonally adjacent. Find the minimum possible sum.

Problem:Minimum Falling Path SumMedium

dp[r][c] = matrix[r][c] + min(dp[r-1][c-1], dp[r-1][c], dp[r-1][c+1])

step 1 / 8

dp over the 3x3 matrix — dp[r][c] = min sum of a falling path reaching this cell

Row 0 needs no work: a path can START at any of these 3 cells, so their falling-path sum is just the cell itself.

Pseudocode
1FUNCTION minFallingPathSum(matrix):
2  n <- LENGTH(matrix)
3  dp <- COPY(matrix)
4  FOR r FROM 1 TO n-1:
5    FOR c FROM 0 TO n-1:
6      best <- dp[r-1][c]
7      IF c > 0: best <- MIN(best, dp[r-1][c-1])
8      IF c < n-1: best <- MIN(best, dp[r-1][c+1])
9      dp[r][c] <- dp[r][c] + best
10  RETURN MIN(dp[n-1])

← / → step · space play · Home restart

Every step in words

Show all 8 steps
  1. Row 0 needs no work: a path can START at any of these 3 cells, so their falling-path sum is just the cell itself.
  2. Best row above cell [1][0] is 1 (left edge — no diagonal-left neighbor), so dp[1][0] = 6 + 1 = 7.
  3. Best row above cell [1][1] is 1, so dp[1][1] = 5 + 1 = 6.
  4. Best row above cell [1][2] is 1 (right edge — no diagonal-right neighbor), so dp[1][2] = 4 + 1 = 5.
  5. Best row above cell [2][0] is 6 (left edge — no diagonal-left neighbor), so dp[2][0] = 7 + 6 = 13.
  6. Best row above cell [2][1] is 5, so dp[2][1] = 8 + 5 = 13.
  7. Best row above cell [2][2] is 5 (right edge — no diagonal-right neighbor), so dp[2][2] = 9 + 5 = 14.
  8. The last row now holds every path's total; its minimum, dp[2][0] = 13, is the answer.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Minimum Falling Path Sum in the editorAll Dynamic Programming problemsBack to roadmap