LeetCode_64. Minimum Path Sum

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

Minimum Path Sum - LeetCode

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]