Leetcode Python - 64. Minimum Path Sum

Leetcode #64 - Minimum Path Sum

이번에는 특정 챕터별로 문제들을 풀어보겠습니다. matrix을 집중적으로 풀어보겠습니다.

리트코드의 문제 64 ‘Minimum Path Sum’을 파이썬으로 풀어 보도록 하겠습니다.

일반 dfs로는 time limit이 나와 discuss를 보도록 하겠습니다.. tc : O(2^(m)) [m과 n이 같을 때]

포인트는 첫 row와 첫 column을 합들로 값을 변경해주고, 나머지 부분은 위나 왼쪽에서 작은 값으로 더해주면 됩니다.

전체 코드는 아래와 같습니다.

class Solution:
    def minPathSum(self, grid):
        if not grid:
            return 0
        m,n = len(grid), len(grid[0])
        for i in range(1, m):
            grid[i][0] = grid[i-1][0] + grid[i][0]
        for i in range(1, n):
            grid[0][i] = grid[0][i-1] + grid[0][i]
        for i in range(1, m):
            for j in range(1, n):
                grid[i][j] = min(grid[i-1][j], grid[i][j-1]) + grid[i][j]
        return grid[-1][-1]

시간복잡도는

• O(mn) : 모든 element를 방문

공간복잡도는

• O(1) : on place