[알고리즘/백준] 11048: 이동하기(python)

이전의 왼쪽, 오른쪽, 대각선 칸들 중 가장 큰 수를 찾고 현재 칸의 수를 더한다.

dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 현재 수

N, M = map(int, input().split())
a = list(list(map(int, input().split())) for _ in range(N))
dp = [[0] * (M+1) for _ in range(N+1)]
for i in range(1, N+1):
    for j in range(1, M+1):
        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + a[i-1][j-1]
print(dp[N][M])