Minimum Shifted Falling Path Sum

Problem Statement

Consider a square matrix of integers called matrix. A falling path with shifts involves selecting exactly one number from each row such that no two chosen numbers from adjacent rows share the same column index.

Your task is to find the smallest possible sum of such a falling path.

Examples

Example 1:
Input: matrix = [[2,3,1],[5,6,4],[9,7,8]]
Output: 12
Explanation:
Possible falling paths include:
[2,6,7], [2,6,8], [2,4,7], [2,4,9],
[3,5,7], [3,5,8], [3,4,9], [3,4,7],
[1,5,7], [1,5,9], [1,6,8], [1,6,9]
The minimum sum path is [1,5,6], which sums up to 12.

Example 2:
Input: matrix = [[-1,0,2],[-3,5,1],[4,-2,3]]
Output: 0
Explanation:
Some falling paths are:
[-1,5,-2], [-1,1,4], [0,-3,3], [0,1,4], [2,-3,-2], [2,5,4]
The smallest sum path is [0, -3, 3] with sum 0.

Constraints

• The size of the matrix is between 2 and 180 (inclusive) for both rows and columns.
• Each element in the matrix is an integer between -100 and 100 inclusive.