알고리즘/Leetcode
LeetCode_64. Minimum Path Sum
꼼지락꼼지락
2020. 12. 21. 22:23
leetcode.com/problems/minimum-path-sum/
Minimum 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.
M x N 사이즈의 table을 이용( all zero),
(r,c) 칸으로 이동할수 있는 경우는 바로 위에칸(r-1,c)에서 아래로 이동하거나 왼쪽 칸(r,c-1)에서 오른쪽으로이동하는 경우만 존재 함, 따라서 (r,c)까지 이동 가능한 경우에서 최소값을 선택
table[r][c] = min(table[r-1][c], table[r][c-1]) + grid[r][c]
Down Right
또한 r=0 인 column들의 이동 방법은 이전 column에서의 이동 밖에 없으므로 이전 column 값을 누적하여 초기화, c=0인 모든 row에 대해서도 마찬가지로 초기화 진행
(r,c) = (1,1) 부터 for 문을 돌며 table update
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
if m == 1 and n == 1:
return grid[0][0]
table = [[0]*n for _ in range(m)]
table[0][0] = grid[0][0]
for r in range(1,m):
table[r][0] = table[r-1][0] + grid[r][0]
for c in range(1,n):
table[0][c] = table[0][c-1] + grid[0][c]
for r in range(1,m):
for c in range(1,n):
table [r][c] = min(table[r-1][c], table[r][c-1]) + grid[r][c]
return table[-1][-1]