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
Top comments (0)