LeetCode 풀기 - 64. Minimum Path Sum

64. Minimum Path Sum

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

Minimum Path Sum - LeetCode

문제)

솔루션1) iterative

Bottom-up 방식으로 풀어 나갑니다.

 

먼저 0행을 초기화합니다.

0행 초기화

0열을 초기화합니다.

0열 초기화

이제 m-1행, n-1을 향해서 순차적으로 채워나갑니다.

채워 나갈 때 최소 sum을 구하면서 채워 나갑니다.

예를 들어 grid[1][1]은 grid[1][0]과 grid[0][1]에서 최소값인 2를 선택해서 자기 자신 5와 더해서 7이 됩니다.

이를 끝까지 반복해 나갑니다.

 

class Solution:
    def minPathSum(self, grid):
        # iterative
        m, n = len(grid), len(grid[0])

        # 첫번째 행 초기화
        for col in range(1, n):
            grid[0][col] = grid[0][col - 1] + grid[0][col]

        # 첫번째 열 초기화
        for row in range(1, m):
            grid[row][0] = grid[row - 1][0] + grid[row][0]

        # bottom-up
        for row in range(1, m):
            for col in range(1, n):
                grid[row][col] += min(grid[row][col-1], grid[row-1][col])

        return grid[m-1][n-1]

솔루션2) iterative 개선

import math
class Solution:
    def minPathSum(self, grid):
        m, n = len(grid), len(grid[0])
        memo = [[0] * n for i in range(m)]
        memo[0][0] = grid[0][0]
        
        for r in range(m):
            for c in range(n):
                if r == 0 and c == 0:
                    continue
                
                left = memo[r][c-1] if c > 0 else math.inf
                up = memo[r-1][c] if r > 0 else math.inf
                memo[r][c] = min(left, up) + grid[r][c]
        
        return memo[m-1][n-1]

 

솔루션3) Dynamic Programming

동적 계획법을 이용해서 풉니다.

 

점화식은 아래와 같은 형식입니다.

f(row, col) = min(f(row-1, col), f(row, col-1) + grid[row][col]

 

memo 변수를 하나 추가해서 이전에 계산 했던 기록을 저장합니다.

class Solution:
    def minPathSum(self, grid):        
        # Dynamic Programming
        
        m, n = len(grid), len(grid[0])
        memo = [[-1]*n for i in range(m)]
        memo[0][0] = grid[0][0]

        for col in range(1, n):
            memo[0][col] = memo[0][col-1] + grid[0][col]

        for row in range(1, m):
            memo[row][0] = memo[row - 1][0] + grid[row][0]

        def dp(row, col):
            if memo[row][col] != -1:
                return memo[row][col]
            memo[row][col] = min(dp(row-1, col), dp(row, col-1)) + grid [row][col]
            return memo[row][col]

        return dp(m-1, n-1)