[동적계획법] Matrix 행렬 경로 문제 (파이썬)

문제:

정수들이 저장된 m*n 행렬에서  

(0,0)에서 (m, n)까지 이동할때 방문한 칸에 있는 정수의 합 중 최소값 찾기

오른쪽, 아래쪽으로만 이동 가능

 

가로 m

세로 n

행렬 입력

 

ex

 

3 3
011
111
110

 

 

m, n = map(int, input().split()) 
a = []
for i in range(n):
    a.append(list(map(int, input())))

for i in range (n):
    for j in range(m):
        if i == 0 and j == 0:
            continue
        elif j == 0:
            a[i][j] += a[i-1][j]
        elif i == 0:
            a[i][j] += a[i][j-1]
        else:
            a[i][j] += min(a[i-1][j], a[i][j-1])
            

print(a[n-1][m-1])

 

프로그래머스나 백준 정수삼각형 문제도 비슷한 방식으로 풀어낼 수 있음