LeetCode: 64. Minimum Path Sum

 

가장 먼저 떠오르는 방법은 완전 탐색

--> Time Limit Exceeded

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        n, m = len(grid), len(grid[0])
        dp = [[int(1e9)] * m for _ in range(n)]
        self.explorer(dp, grid, 0, 0, 0)
        return dp[n-1][m-1]
        
    def explorer(self, dp, grid, i, j, nowSum):
        nowSum += grid[i][j]
        if i == len(grid) - 1 and j == len(grid[0]) - 1:
            dp[i][j] = min(dp[i][j], nowSum)
            return
        if nowSum < dp[i][j]:
            dp[i][j] = nowSum
            if i + 1 <= len(grid) - 1:
                self.explorer(dp, grid, i+1, j, nowSum)
            if j + 1 <= len(grid[0]) - 1:
                self.explorer(dp, grid, i, j+1, nowSum)

 

오른쪽과 아래쪽으로만 움직일 수 있다는 제약을 이용한다.

dp[i][j]: grid[i][j]까지 오는 데 걸리는 최소 비용

dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        n, m = len(grid), len(grid[0])
        dp = [[0] * m for _ in range(n)]
        dp[0][0] = grid[0][0]
        for i in range(1, m):
            dp[0][i] = dp[0][i-1] + grid[0][i]
        for i in range(1, n):
            dp[i][0] = dp[i-1][0] + grid[i][0]
        for i in range(1, n):
            for j in range(1, m):
                dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
        return dp[n-1][m-1]