aboutsummaryrefslogtreecommitdiff
path: root/min_falling_path_sum.py
blob: 29eff1b6cfa913d9bbe8ecb80c3853f36e037c5c (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
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]]))