Given an n x n integer matrix, return the minimum sum of any falling path. A falling path starts at any cell in the first row and chooses the cell directly below or diagonally below-left/right at each step (column changes by at most 1).
We use analytics and advertising cookies to understand how the site is used and whether our ads on Facebook and Instagram work. They are set only if you accept. See our Privacy Policy for details.
Given an n x n integer matrix, return the minimum sum of any falling path. A falling path starts at any cell in the first row and chooses the cell directly below or diagonally below-left/right at each step (column changes by at most 1).
A medium dynamic programming problem, graded against 7 test cases (5 of them hidden).
Overlapping subproblems solved once and reused - the pattern candidates fear most.
Reach for it when you see: "Number of ways", "minimum/maximum cost", or a recursion that recomputes the same state.
More Dynamic Programming problems →Row-by-row DP. `dp[j]` holds the minimum falling-path sum ending at column `j` of the current row, computed from the previous row's `dp[j-1]`, `dp[j]`, and `dp[j+1]`. The answer is the minimum over the last row.
Time: O(n²). Space: O(n).
The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.
Read off this problem's own test suite, so these are the cases a submission actually has to survive.
These apply to the pattern as a whole, not just this problem.