Minimum Falling Path Sum II

Hard

Given an n x n integer grid, a falling path with non-zero shifts chooses exactly one element from each row such that no two chosen elements in adjacent rows are in the same column. Return the minimum sum of such a falling path.

Example 1

Input:  grid = [[1,2,3],[4,5,6],[7,8,9]]
Output: 13

Example 2

Input:  grid = [[7]]
Output: 7

Constraints

• n == grid.length == grid[i].length
• 1 <= n <= 200
• -99 <= grid[i][j] <= 99