LeetCode #931: Minimum Falling Path Sum
β’ 83 words β’ 1 min β’ updated
LeetCode #931: Minimum Falling Path Sum:
python
class Solution:
def minFallingPathSum(self, matrix: List[List[int]]) -> int:
m = len(matrix)
n = len(matrix[0])
from functools import cache
@cache
def solve(i, j):
if i < 0 or j < 0 or i >= m or j >= n:
return float('inf')
if i == 0:
return matrix[0][j]
return matrix[i][j] + min(
solve(i - 1, j - 1),
solve(i - 1, j),
solve(i - 1, j + 1),
)
return min(solve(m - 1, col) for col in range(n))