Minimum Falling Path Sum

Given an n x n array of integers matrix, return the minimum sum of any falling path through matrix.

A falling path starts at any element in the first row and chooses the element in the next row that is either directly below or diagonally left/right. Specifically, the next element from position (row, col) will be (row + 1, col - 1), (row + 1, col), or (row + 1, col + 1).

Example 1:

Input: matrix = [[2,1,3],[6,5,4],[7,8,9]]
Output: 13
Explanation: There are two falling paths with a minimum sum as shown.

Example 2:

Input: matrix = [[-19,57],[-40,-5]]
Output: -59
Explanation: The falling path with a minimum sum is shown.

Constraints:

• n == matrix.length == matrix[i].length
• 1 <= n <= 100
• -100 <= matrix[i][j] <= 100

SOLUTION:

class Solution:
    def minSum(self, matrix, i, j, m, n):
        if i == m - 1:
            return matrix[i][j]
        if (i, j) in self.cache:
            return self.cache[(i, j)]
        minPath = float('inf')
        for col in [j - 1, j, j + 1]:
            if 0 <= col < n:
                minPath = min(minPath, matrix[i][j] + self.minSum(matrix, i + 1, col, m, n))
        self.cache[(i, j)] = minPath
        return minPath

    def minFallingPathSum(self, matrix: List[List[int]]) -> int:
        m = len(matrix)
        n = len(matrix[0])
        self.cache = {}
        minPath = float('inf')
        for i in range(n):
            minPath = min(minPath, self.minSum(matrix, 0, i, m, n))
        return minPath