LeetCode_931. Minimum Falling Path Sum

leetcode.com/problems/minimum-falling-path-sum/

Minimum Falling Path Sum - LeetCode

Solution1. 

 

최종 목적지에서부터 역으로 최소가 되는 값을 찾아 table(r,c)에 기록하는 방법으로 접근

(지금 생각 하니 최초 출발지에서 시작 하든 동일하네...;;)

 

row = 2 : (2,0)에서의 최소값은 7, (2,2)에서의 최소값은 8, (2,2)에서의 최소값은 9, → A[2][:] 와 동일

row = 1 :

       (1,0) 에서의 최소값은 min(table[2][0], table[2][1]) + A[1][0] → 11

       (1,1) 에서의 최소값은 min(table[2][0], table[2][1], table[2][2]) + A[1][1] → 12

       (1,3) 에서의 최소값은 min(table[2][1], table[2][2]) + A[1][2] → 14

row = 0:

       (0,0) 에서의 최소값은 min(table[1][0], table[1][1]) + A[0][0] → 12

       (0,1) 에서의 최소값은 min(table[1][0], table[1][1], table[1][2]) + A[0][1] → 13

       (0,3) 에서의 최소값은 min(table[1][1], table[1][2]) + A[0][2] → 15

 

최종 minimum path sum 0번째 row의 최소값 → min(table[0])

class Solution:
    def minFallingPathSum(self, A: List[List[int]]) -> int:
        table = A[:]
        m,n = len(A), len(A[0])
        
        for r in range(m-2, -1, -1):
            for c in range(0,n):
                if c-1 < 0:
                    table[r][c] += min(table[r+1][c:c+2])
                elif c+1 > n:
                    table[r][c] += min(table[r+1][c-1:c+1])
                else:
                    table[r][c] += min(table[r+1][c-1:c+2])
                
        return min(table[0])