[이코테][Python][DP] 금광

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

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

#arr 초기화
arr = []
for i in range(n):
  arr.append(list(map(int, input().split())))

for i in range(n):
  dp[i][0] = arr[i][0]

for j in range(1, m):
  for i in range(n):
    if (i == 0):
      dp[i][j] = max(dp[i + 1][j - 1], dp[i][j - 1]) + arr[i][j]
    elif (i == n - 1):
      dp[i][j] = max(dp[i - 1][j - 1], dp[i][j - 1]) + arr[i][j]
    else:
      dp[i][j] = max(dp[i - 1][j - 1], dp[i][j - 1],
                     dp[i + 1][j - 1]) + arr[i][j]

k = 0
for i in range(n):
  k = max(k, dp[i][m - 1])

print(k)

 

점화식이 쉬워서 쉽게 풀어낸 문제다.