DEV Community

Abhishek Chaudhary

Posted on

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
``````