Minimum Falling Path Sum
MediumBest of three cells above
Problem
Find the minimum sum of a falling path through a matrix (each step goes down to an adjacent column).
Falling down, each cell adds the smallest of the three cells directly above it.
The idea
A cell can be entered from directly above or from either diagonal, so its best total is its own value plus the minimum of those three. Sweep row by row and the answer is the smallest value in the final row.
The trick
- Guard the column edges, where only two predecessors exist.
- Answer = min over the last row, not the last cell.
- O(rows × cols) with one row of storage.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — [[2,1,3],[6,5,4],[7,8,9]] Values: 2, 1, 3.
1dp[i][j]=a[i][j]+min(dp[i-1][j-1],dp[i-1][j],dp[i-1][j+1])Input
- array
- [2, 1, 3]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- matrix = [[2,1,3],[6,5,4],[7,8,9]]
- Output:
- 13
- Explanation:
- 1→4→8? best falling path sums to 13.
Example 2
- Input:
- matrix = [[-19,57],[-40,-5]]
- Output:
- -59
- Explanation:
- Best path is -59.
Example 3
- Input:
- matrix = [[5]]
- Output:
- 5
- Explanation:
- One cell.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.