-
LeetCode_931. Minimum Falling Path Sum알고리즘/Leetcode 2020. 12. 22. 00:22
leetcode.com/problems/minimum-falling-path-sum/
Minimum Falling Path Sum - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
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])
'알고리즘 > Leetcode' 카테고리의 다른 글
LeetCode_96. Unique Binary Search Trees (0) 2020.12.21 LeetCode_64. Minimum Path Sum (0) 2020.12.21 LeetCode_63. Unique Paths II (0) 2020.12.21 LeetCode_62. Unique Paths (0) 2020.12.21 LeetCode_486. Predict the Winner (0) 2020.12.18