1143. Minimum Falling Path Sum

Given a square matrix, a falling path starts at any cell in the first row and chooses the cell directly below or diagonally below-left or below-right at each step. Return the minimum sum of a falling path from the top row to the bottom row. The input is JSON {matrix}.

Input: JSON {matrix}.

Output: Integer — the minimum falling path sum.

Examples

Input: {"matrix":[[2,1,3],[6,5,4],[7,8,9]]}
Output: 13
Explanation: 1->5->7 sums to 13.

Input: {"matrix":[[-19,57],[-40,-5]]}
Output: -59
Explanation: -19 + -40 = -59.

Input: {"matrix":[[7]]}
Output: 7
Explanation: Single cell.

Constraints

• 1<=n<=100

Asked by