코딩테스트 고득점 Kit - 동적계획법(Dynamic Programming) 2 (Level 3)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
from itertools import product
from collections import defaultdict

def solution(triangle):
    n = len(triangle)
    d = {r: [e[-(r+1)] if r < len(e) else -1 for e in triangle] for r in range(n)}


    m = [[-1]*n for _ in range(n)]
    m[0][0] = d[0][0]

    for i in range(n):
        for j in range(i, n):
            if i == j == 0:
                continue

            try:
                max1 = m[i][j-1]
            except:
                max1 = -1
            try:
                max2 = m[i-1][j-1]
            except:
                max2 = -1

            rst = max(max1, max2) + d[i][j]
#             print(f"m[{i},{j}]: max({max1}, {max2}) + {d[i][j]} = {rst}")

            if max1 == max2 == -1:
                continue

            m[i][j] = rst

    return max([e[-1] for e in m])