Given an n x n matrix of integers, return the minimum sum of a falling path, where each step may move straight down, down-left, or down-right. Pattern focus: Direction variants. The allowed transitions define the dynamic programming recurrence.
matrix is an n x n matrix
minimum falling path sum
Example 1:
Input:
matrix = [[2,1,3],[6,5,4],[7,8,9]]
Output:
13
Explanation:
The best falling path has sum 13.
Example 2:
Input:
matrix = [[-19,57],[-40,-5]]
Output:
-59
Explanation:
The minimum sum is -59.
Example 3:
Input:
matrix = [[1]]
Output:
1
Explanation:
A single-cell matrix returns 1.