[PG] 정수 삼각형

문제

me

def solution(triangle):
    for i in range(len(triangle)-1):
        triangle[i+1][0]+=triangle[i][0]
        triangle[i+1][len(triangle[i])]+=triangle[i][len(triangle[i])-1]
        for j in range(len(triangle[i])-1):
            triangle[i+1][j+1]+=max(triangle[i][j],triangle[i][j+1])
    return max(triangle[-1])

others

• 프로그래머스 다른 사람 풀이

def solution(triangle):
    memo = {}
    answer = f(triangle, 0, 0, memo)
    return answer

def f(triangle, i, j, memo):
    if i == len(triangle)-1:
        return triangle[i][j]

    if (i,j) in memo:
        return memo[(i,j)]

    a = f(triangle, i+1, j, memo)
    b = f(triangle, i+1, j+1, memo)
    x = triangle[i][j] + max(a, b)

    memo[(i,j)] = x

    return x