[Python] LeetCode - 64. Minimum Path Sum

LeetCode 64번 Minimum Path Sum 문제는 (n,m)칸 까지 가는 최소경로를 구하는 문제다. 난이도는 Medium이며 DP를 통해 해결할 수 있다.

 

리트코드 64번 Minimum Path Sum 문제 정보

알고리즘 분류

- Dynamic Programming

난이도

- Medium

 

문제 요약

• 0이상의 정수로 채워진 mxn 그리드가 주어진다.
• 맨 왼쪽 위칸에서 맨 오른쪽 아래칸까지 가는 최소 경로를 구하라.
  • 단, 오른쪽 또는 아래로만 이동할 수 있다.

 

문제 풀이 과정

• 각 칸까지 이동하기 위한 최솟값을 구한다.
  • 왼쪽 or 위쪽에 저장된 값 중 더 작은 값을 더한다.

코드

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        H, W = len(grid), len(grid[0])

				# 1행 처리
        for c in range(1, W):
            grid[0][c] += grid[0][c-1]
        
				# 1열 처리
        for r in range(1, H):
            grid[r][0] += grid[r-1][0]

        for r in range(1, H):
            for c in range(1, W):
                grid[r][c] += min(grid[r][c-1], grid[r-1][c])
        
        return grid[-1][-1]

• 시간복잡도: O(nm)
• 공간복잡도: O(1) - 추가 공간 X