HI.py

# 종만북에서 풀었던 문제. 삼각형 모양만 다르다.
# cache[i][j] 보다 f 스트링을 사용한 1중 dict 가 훨씬 빠르다.
# 이게 반복으로 풀 수 있는 문제인가?

cache = {}


def move(triangle, i, j):
    '''
    현재 위치에서 내려갔을 떄 얻을 수 있는 최댓값을 반환합니다.
    '''

    key = f'{i} {j}'

    if key in cache:
        return cache[key]

    if i > len(triangle) - 1:
        return 0

    if j > len(triangle[i]) - 1:
        return 0

    cache[key] = triangle[i][j] + max(move(triangle, i + 1, j), move(triangle, i + 1, j + 1))

    return cache[key]


def solution(triangle):
    return move(triangle, 0, 0)