#931

Minimum Falling Path Sum

specialist · 695 · lc medium +30 · verified · 60.8% accepted · 6,975 likes · top 60%

Description

Given an n x n integer matrix matrix, return the minimum possible sum along a falling path. A falling path begins at any cell in the first row and, at each step, moves to one of the three adjacent cells in the next row — down-left, straight down, or down-right.

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.

Code

1

2

3

class Solution:
    def minFallingPathSum(self, matrix: List[List[int]]) -> int:

class Solution:
    def minFallingPathSum(self, matrix: List[List[int]]) -> int: