Programmers - 정수 삼각형

문제 링크

DP 문제.
d[h][w] : (h,w)에 도착 했을 때 얻을 수 있는 최대 값
d[h][w]에 오는 방법은 2가지가 있다.

1. d[h-1][w]에서 내려오는 방법
2. d[h-1][w-1]에서 내려오는 방법

이 때 d[h][w]는 위 2가지 방법 중 더 큰 값에서 내려온 경우를 고르면 된다.

d[h][w] = max(d[h-1][w],d[h-w][w-1]) + triangle[h][w]

def solution(triangle):
    height = len(triangle)
    d = [[-1 for _ in range(height)] for __ in range(height)]

    d[0][0] = triangle[0][0]
    for h in range(1, height):
        for w in range(h+1):
            d[h][w] = max(d[h][w], d[h-1][w]+triangle[h][w])
            if w-1 >= 0:
                d[h][w] = max(d[h][w], d[h-1][w-1]+triangle[h][w])

    # print(d)

    return max(d[height-1])