<jupyter_start><jupyter_text>Title : 최소비용 길찾기Chapter : Dynamic ProgrammingLink : [YouTube](https://youtu.be/11oqpRgDF9Q)ChapterLink : [PlayList](https://youtube.com/playlist?list=PLDV-cCQnUlIa0owhTLK-VT994Qh6XTy4v)문제: 2d array로 길을 가기 위한 비용이 주어진다. 왼쪽 위에서 오른족 아래까지 도달하기 위한 최소 비용은 얼마인가?<jupyter_code>from typing import List  

def minPathSum(grid: List[List[int]]) -> int:
    rows = len(grid)
    cols = len(grid[0])
    minCost2d = a = [[0] * cols for i in range(rows)]
    
    #initialize 2d cost map
    minCost2d[0][0] = grid[0][0]
    for colIdx in range(1,cols):
      minCost2d[0][colIdx] = grid[0][colIdx] + minCost2d[0][colIdx-1]
    for rowIdx in range(1,rows):
      minCost2d[rowIdx][0] = grid[rowIdx][0] + minCost2d[rowIdx-1][0]
    
    #bottom up DP
    for rowIdx in range (1,rows):
      for colIdx in range (1,cols):
        prevCol = colIdx - 1
        prevRow = rowIdx - 1
        
        upCost = 0 if (prevRow < 0) else minCost2d[prevRow][colIdx]
        leftCost = 0 if (prevCol < 0 ) else minCost2d[rowIdx][prevCol]
        
        prevCost = min(upCost,leftCost)
        cost = prevCost + grid[rowIdx][colIdx]        
        minCost2d[rowIdx][colIdx] = cost
                
    minCost = minCost2d[rows-1][cols-1]    
    return minCost
grid = [[1,3,1,2],[2,4,5,2],[3,4,5,6],[1,5,6,2]]
print('minCost=',minPathSum(grid=grid))<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.14461315979754158, 'fraction_numerical': 0.0455531453362256, 'mean_word_length': 3.1313432835820896, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 6, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '287633', 'license': 'MIT', 'n_tokens_mistral': 614, 'n_tokens_neox': 628, 'n_words': 109, 'path': 'dynamicProgramming/minSumPath.ipynb', 'repo_name': 'NoCodeProgram/CodingTest', 'size': '1383'}