[Leetcode] 64. Minimum Path Sum

문제 바로가기

Dynamic Programming

Bottom up

Time Complexity: O(mn)
Space Complexity: O(mn)

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        memo = grid[:][:]
        for r in range(1, m):
            memo[r][0] += memo[r-1][0]
        for c in range(1, n):
            memo[0][c] += memo[0][c-1]

        for r in range(1, m):
            for c in range(1, n):
                memo[r][c] += min(memo[r-1][c], memo[r][c-1])
        
        return memo[m-1][n-1]

Top down

Time Complexity: O(mn)
Space Complexity: O(mn)

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        memo = [[-1 for _ in range(n)] for _ in range(m)]
        memo[0][0] = grid[0][0]
        for r in range(1, m):
            memo[r][0] = grid[r][0] + memo[r-1][0]
        for c in range(1, n):
            memo[0][c] = grid[0][c] + memo[0][c-1]

        def findPaths(m: int, n: int) -> int:
            if memo[m][n] < 0:
                memo[m][n] = min(findPaths(m - 1, n), findPaths(m, n - 1)) + grid[m][n]
            return memo[m][n]

        return findPaths(m - 1, n - 1)