[n11048] 이동하기 in python

---

dp를 이용하여 푸는 문제

dp 할 때는 n+1, m+1의 배열로 만든다.

그래야 인덱스 처리를 따로 해주지 않아도 에러가 나지 않는다 :) 

 

array 배열

0	0	0	0	0
0	1	2	3	4
0	0	0	0	5
0	9	8	7	6
0	0	0	0	0

 

 

dp 배열

0	0	0	0	0
0	1+0 = 1	2+1 = 3	3+3 = 6	4+6 = 10
0	0+1= 1	0+3 = 3	0+6= 6	5+10=15
0	9+1=10	8+10=18	7+18=25	6+25=31
0	0	0	0	0

 

n, m = map(int, input().split())
array = [list(map(int, input().split())) for _ in range(n)]
dp = [[0 for _ in range(m+1)] for _ in range(n + 1)]

for i in range(1, n+1):
    for j in range(1, m+1):
        dp[i][j] = array[i - 1][j - 1] + max(dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j])

print(dp[n][m])

 

---