다이나믹 프로그래밍(Min Sum Path)

문제: 2d array로 길을 가기 위한 비용이 주어진다. 왼쪽 위에서 오른쪽 아래까지 도달하기 위한 최소 비용은 얼마인가?

 

이전 문제와 다른 점은 2d 라는 것 뿐이다.

다이나믹 프로그래밍(계단 오르기) (tistory.com)

다이나믹 프로그래밍(계단 오르기)

from typing import List

def minPathSum(grid:List[List[int]]) -> int:
    row = len(grid)
    col = len(grid[0])
    costGrid = [[0] * col for i in range(0, row)]

    costGrid[0][0] = grid[0][0]

    for y in range(1, row):
        costGrid[y][0] = costGrid[y -1][0] + grid[y][0]
    for x in range(1, col):
        costGrid[0][x] = costGrid[0][x-1] + grid[0][x]

    # bottom up
    for y in range(1, row):
        for x in range(1, col):
            minVal = min(costGrid[y][x-1], costGrid[y-1][x])
            costGrid[y][x] = minVal + grid[y][x]

    return costGrid[row-1][col-1]

grid = [[1,3,1,2],[2,4,5,2],[3,4,5,6],[1,5,6,2]]
print('minCost=',minPathSum(grid=grid))

출처 : (5) 코딩테스트, 초급, Min Sum Path - YouTube