[Dynamic Programming] 최소 비용 구하기 - 초급

유튭 링ㅋ

 

📋 LeetCode 64번

Minimum Path Sum - LeetCode

    grid                  cost                

[[ 1, 3, 1 ],        [[ 1, 4, 5 ],

  [ 1, 5, 1 ],   →    [ 2, _, _ ],

 [ 4, 2, 1 ]]        [ 6, _, _ ]]

 

2차원 배열인 grid가 grid[x][y]으로 이루어져 있을 때, grid[0][y] 와 grid[x][0] 의 최소 길이는 계산 없이도 알 수 있다. (이동이 down or right로 제한되어있다.)

 

$$ cost[x][y] = min( grid[x-1][y] , grid[x][y-1] ) + grid[x][y] $$

 

피보나치와 비슷한 해결 방법

 

시간 복잡도 : O(n*m)

공간 복잡도 : O(n) → 계산에 사용하는 공간은 O(n) 또는 O(m)

  + 새로운 배열을 만들지 않고 주어진 배열에 그대로 cost를 계산할 수 있다.

 

 

👩🏻‍💻 내 풀이

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        n = len(grid)
        m = len(grid[0])
        
        for i in range(n):
            for j in range(m):
                # print(grid)
                if i == 0 and j == 0:
                    continue
                elif i == 0 and j>0:
                    grid[i][j] = grid[i][j]+grid[i][j-1]
                elif i>0 and j == 0:
                    grid[i][j] = grid[i][j]+grid[i-1][j]
                else:
                    grid[i][j] = min(grid[i-1][j], grid[i][j-1])+grid[i][j]
        
        return grid[n-1][m-1]

지저분하지만 통과!