Pattern visualizer
Minimum Falling Path Sum
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. 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..
dp[r][c] = matrix[r][c] + min(dp[r-1][c-1], dp[r-1][c], dp[r-1][c+1])
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.
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] + best10 RETURN MIN(dp[n-1])
← / → step · space play · Home restart