[Code Kata] 합이 최소가 되는 최단 경로 찾기

Q.

양수로 이루어진 m x n 그리드를 인자로 드립니다. 상단 왼쪽에서 시작하여, 하단 오른쪽까지 가는 길의 요소를 다 더했을 때,가장 작은 합을 찾아서 return 해주세요.

한 지점에서 우측이나 아래로만 이동할 수 있습니다.

Input: [    [1,3,1],    [1,5,1],    [4,2,1] ]

Output: 7

설명: 1→3→1→1→1 의 합이 제일 작음

def min_path_sum(grid):
  sumlist=grid
  m=len(grid)
  n=len(grid[0])

  for i in range(1,m):
    sumlist[i][0]+=sumlist[i-1][0]
  for i in range(1,n):
    sumlist[0][i]+=sumlist[0][i-1]
  
  a=0
  b=0
  c=0
  token=0
  
  for i in range(2,m+n-1):
    for j in range(1,i):

      try:
        sumlist[j][i-j]
        
        try:
          a=sumlist[j-1][i-j]
        except:
          token+=1
          continue
          
        try:
          b=sumlist[j][i-j-1]
        except:
          token+=2
          continue
          
        if token==0:
          c=min(a,b)
          sumlist[j][i-j]+=c
        elif token==1:
          sumlist[j][i-j]+=b
        elif token==2:
          sumlist[j][i-j]+=a
        else:
          continue
        print(token)
        token=0
        
      except:
        continue
  return sumlist[m-1][n-1]