백준 알고리즘 9844번 Gecko(python)

기본적인 다이나믹 프로그래밍 문제이다.

h, w = map(int, input().split())
li = [list(map(int, input().split())) for _ in range(h)]
dp = [[0]*w for _ in range(h)]
dp[0] = li[0]
for i in range(1, h):
    for j in range(w):
        if j == 0:
            dp[i][j] = li[i][j] + max(dp[i-1][0], dp[i-1][1])
        elif j == w-1:
            dp[i][j] = li[i][j] + max(dp[i-1][j-1], dp[i-1][j])
        else:
            dp[i][j] = li[i][j] + max(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1])
print(max(dp[-1]))