#1289
Minimum Falling Path Sum II
expert · 1115 · lc hard +32 · verified · 63.2% accepted · 2,374 likes · top 65%
Description
In an n x n integer matrix grid, a falling path with non-zero shifts selects exactly one element per row so that no two consecutive rows share the same column index.
Return the minimum possible sum of such a path.
Example 1:
Input: grid = [[1,2,3],[4,5,6],[7,8,9]]
Output: 13
Explanation:
The possible falling paths are:
[1,5,9], [1,5,7], [1,6,7], [1,6,8],
[2,4,8], [2,4,9], [2,6,7], [2,6,8],
[3,4,8], [3,4,9], [3,5,7], [3,5,9]
The falling path with the smallest sum is [1,5,7], so the answer is 13.
Example 2:
Input: grid = [[7]]
Output: 7
Code
1
2
3