[백준/11048/파이썬] 이동하기 - DP

---

소스코드

n, m = map(int, input().split())

s = []

dp = [[0] * (m + 1) for i in range(n + 1)]

for i in range(n):

    s.append(list(map(int, input().split())))

for i in range(1, n + 1):

    for j in range(1, m + 1):

        dp[i][j] = s[i - 1][j - 1] + max(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])

print(dp[n][m])

---

알고리즘

DP는 점화식을 잘 세우면 되는것 같아요~ 이제 슬슬 깨닫게 되는것 같습니다.

1	2	3
6	5	7
7	8	9
12	11	10

이런 입력을 받았을 때 DP 리스트에는 다음과 같이 채워지게 됩니다.

0	0	0	0
0	1	3	6
0	7	12	19
0	14	22	31
0	26	37	47

dp[i][j] = s[i - 1][j - 1] + max(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])

채워질 부분dp[i][j]  = 채워질부분 s[i - 1][j - 1] + 갈 수 있는 애들 중 최대 max(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])를 더한 식입니다. 표로 그려보니 더 잘 이해할 수 있었습니다.