Minimum Falling Path Sum
Medium · Dynamic Programming · Array · Dynamic Programming · Matrix
Problem
You are given an n x n integer matrix matrix. A falling path starts at any cell in the first row and moves down one row at a time. From cell (row, col) the next cell is (row + 1, col - 1), (row + 1, col) or (row + 1, col + 1), as long as it stays inside the matrix.
Return the smallest sum of the values along any falling path.
Examples
Input: matrix = [[3,1,4],[1,5,9],[2,6,5]] Output: 4
Go 1 (middle) -> 1 (left) -> 2 (left) for a sum of 4.
Input: matrix = [[-5]] Output: -5
The only path is the single cell.
Input: matrix = [[1,2],[3,4]] Output: 4
Take 1 and then 3 directly below it.
Constraints
- n == len(matrix) == len(matrix[i])
- 1 <= n <= 100
- -100 <= matrix[i][j] <= 100
Approaches
- Baseline: try every path — time O(n · 3^n), space O(n)
Follow-up
Read from the bottom up, the same recurrence gives the cheapest path from each cell down. The use cases widen the moves: one allows any column except the same one, where the two smallest sums of each row keep the work at O(n²); the other allows every column but puts a price on each move.
Related problems
Start free on Cariara · Coding problems · System design studio
