blob: 1cd1c1955dd0fad6b6e0e8d51e3b520022dd189e (
plain)
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
|
# 1289. Minimum Falling Path Sum II
from heapq import nsmallest
"""
given a 'n * n' integer matrix 'grid' return the minimum sum of a falling
path with non zero shifts. a falling path with non zero shifts is a choice of
exactly one element from each row of 'grid' such that no two elements chosen
in adjacent rows are in the same column
"""
class Solution(object):
def minFallingPathSum(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
for i in range(1, len(grid)):
r = nsmallest(2, grid[i - 1])
for j in range(len(grid[0])):
grid[i][j] += r[1] if grid[i - 1][j] == r[0] else r[0]
return min(grid[-1])
if __name__ == "__main__":
obj = Solution()
print(obj.minFallingPathSum(grid=[[1, 2, 3], [4, 5, 6], [7, 8, 9]]))
print(obj.minFallingPathSum(grid=[[7]]))
|