[LeetCode] 64. Minimum Path Sum 풀이 및 코드

문제

왼쪽 상단 코너에서 오른쪽 하단 코너까지 각 칸에 적힌 수의 합이 최소인 경로를 구해라.

---

풀이

이 문제를 푸는 데 중요한 포인트는 특정 칸까지의 최소인 경로는 하나만 구하면 된다는 점이다. 그 경로가 어떤 경로인지는 중요하지 않고, 수의 합이 최소라는 점만 중요하다. 따라서 최소의 합을 내는 경로를 구했다면 그 최소의 합만 저장하고, 경로는 저장할 필요가 없다.

따라서 이 문제는 동적 프로그래밍으로 풀기에 적합하다. 각 칸까지의 경로의 최소 합을 저장하고, 다음 칸의 값을 구할 때 이전 값들을 사용하면 된다. 즉, dp[i][j] = min(dp[i-1][j], dp[i][j-1])+ grid[i][j]. (물론, 예외처리는 해주어야 한다.)

---

코드

class Solution(object):
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        m, n = len(grid), len(grid[0])
        dp = [[0 for _ in range(n)] for _ in range(m)]
        
        for i in range(m):
            for j in range(n):
                if i == 0 and j == 0:
                    dp[i][j] = grid[i][j]
                else:
                    if i > 0 and j > 0:
                        dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
                    elif i > 0:
                        dp[i][j] = dp[i-1][j] + grid[i][j]
                    else:
                        dp[i][j] = dp[i][j-1] + grid[i][j]

        return dp[m-1][n-1]

---

리트코드 제출 결과

---

출처

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