[Programmers | Level 3] 정수 삼각형 (Python)

https://programmers.co.kr/learn/courses/30/lessons/43105

코딩테스트 연습 - 정수 삼각형

def solution(triangle):
    n = len(triangle[-1])
    d = [[0] * i for i in range(1, n + 1)]

    d[0][0] = triangle[0][0]

    for i in range(1, n):
        d[i][0] = d[i - 1][0] + triangle[i][0]
        d[i][-1] = d[i - 1][-1] + triangle[i][-1]

    for i in range(2, n):
        for j in range(1, i):
            d[i][j] = max(d[i - 1][j], d[i - 1][j - 1]) + triangle[i][j]

    return max(d[n - 1])

DP를 이용하여 풀었다.

주어진 삼각형과 같은 모양의 이차원 배열을 선언하고,

위에서 부터 탐색하면서 그 위치에서 거쳐온 숫자의 최댓값을 저장한다.

부분문제가 다음 부분문제에 이용되고 있다.

bottom up 방식으로 해결하였다.