Minimum Falling Path Sum

Choose one entry in each row of the square matrix, starting anywhere in the first row. From column c, the next row may use column c-1, c, or c+1, provided it remains inside the matrix. Add the chosen entries and return the smallest possible sum. Negative entries are allowed.

Hatched cells show one minimum-sum falling path.

Example 1:

Input: matrix = [[1,9],[9,2]]

Output: 3

Explanation: Start at the first row, column 0, with value 1, then move diagonally right to value 2. Their sum is 3, smaller than every other path.

Example 2:

Input: matrix = [[2,-3],[4,-5]]

Output: -8

Explanation: Start at -3 and move directly below to -5. The sum is -8.

Example 3:

Input: matrix = [[7]]

Output: 7

Explanation: There is only one row and one entry, so the path consists of 7 alone.

Constraints:

• 1 <= matrix.length <= 100
• Every row has matrix.length entries.
• -100 <= matrix[i][j] <= 100