문제)

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

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

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

Output: 7

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

itertools라는 python 모듈안에 combination, permutation 모듈을 사용하면 쉽게 풀 수 있었다. 우리가 흔히 최단경로 문제를 풀면 조합과 순열을 많이 사용한다.
조합의 경우 👉 총 이동 횟수중에 ➡️로 이동하는 경우를 뽑거나 (혹은 ⬇️의 경우를 뽑음)
순열의 경우 👉 ➡️ ⬇️ 의 중복 순열의 개수를 구한다.

• 우하향 경로의 경우기 때문에 ➡️, ⬇️ 를 사용한다.

def min_path_sum(grid):
  
  from itertools import combinations

  arr=[i for i in range(len(grid)+len(grid[0])-2)]
  cases=list(combinations(arr,len(grid[0])-1)) 
  result=[]
  for case in cases:
    a=0
    b=0
    add=grid[0][0]
    for i in range(len(grid)+len(grid[0])-2):
      if i in case:
        a+=1
        add+=grid[b][a]
      else:
        b+=1
        add+=grid[b][a]
    result.append(add)
  return (min(result))