Given a square integer matrix matrix of size n by n, return the minimum possible sum of a falling path through matrix.

A falling path starts at any element in the first row and chooses one element from each subsequent row. If the current element is at row r and column c, the next element must be in row r + 1 and in column c, c - 1, or c + 1, as long as the chosen column stays within the matrix bounds.

Constraints:

• n == matrix.length == matrix[i].length

• $1 \leq$ n $\leq 100$

• $-100 \leq$ matrix[i][j] $\leq 100$

Input: matrix = [[2,1,3],[6,5,4],[7,8,9]]-List[List[int]]
Output: 13-int
Explanation: A minimum falling path is 1 -> 4 -> 8 (starting at row 0, col 1), with sum 1 + 4 + 8 = 13.

Input: matrix = [[-19,57],[-40,-5]]-List[List[int]]
Output: -59-int
Explanation: Start at -19 (row 0, col 0), then move down to -40 (row 1, col 0), for a sum of -19 + (-40) = -59.

Input: matrix = [[5]]-List[List[int]]
Output: 5-int
Explanation: With n = 1, the only falling path is the single element itself, so the minimum sum is 5.

Input: matrix = [[10,3,1],[2,100,2],[1,2,10]]-List[List[int]]
Output: 6-int
Explanation: A minimum falling path is 3 -> 2 -> 1 (row 0 col 1 → row 1 col 0 → row 2 col 0), with sum 3 + 2 + 1 = 6.

Input: matrix = [[0,0,0],[0,-1,0],[0,0,0]]-List[List[int]]
Output: -1-int
Explanation: Choose 0 in the first row, move to -1 in the middle of the second row, then to any 0 in the last row, giving the minimum possible sum of -1.

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.