1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
# 931. Minimum Falling Path Sum
"""
given an 'n 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 choose 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)'.
"""
class Solution(object):
def minFallingPathSum(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: int
"""
grid = matrix
for i in range(1, len(grid)):
for j in range(len(grid[i])):
if i - 1 >= 0 and j - 1 >= 0:
p1 = grid[i - 1][j - 1]
else:
p1 = float("inf")
if i - 1 >= 0:
p2 = grid[i - 1][j]
else:
p2 = float("inf")
if i - 1 >= 0 and j + 1 <= len(grid[0]) - 1:
p3 = grid[i - 1][j + 1]
else:
p3 = float("inf")
grid[i][j] += min(p1, p2, p3)
return min(grid[len(grid) - 1])
if __name__ == "__main__":
obj = Solution()
print(obj.minFallingPathSum(matrix=[[2, 1, 3], [6, 5, 4], [7, 8, 9]]))
print(obj.minFallingPathSum(matrix=[[-19, 57], [-40, -5]]))
|