[프로그래머스][동적계획법] 정수 삼각형

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

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

간단한 dp문제. 숫자 하나 기준으로 윗줄의 left right 숫자를 더하며 가장 큰것을 선택해 나가면 된다.

 

다른사람 풀이보니 한줄에 풀었던데 그런건 어케하는건지..

 

 

def solution(triangle):
    answer = 0
    length = len(triangle)
    dp = [ [0] * i for i in range(1, length + 1)]
    dp[0][0] = triangle[0][0]
    
    for i in range(1, length):
        for j in range(i+1):
            right = j
            left = j - 1
            if right <= i-1:
                dp[i][j] = max(dp[i][j], triangle[i][j] + dp[i-1][right])
            if left >= 0:
                dp[i][j] = max(dp[i][j], triangle[i][j] + dp[i-1][left])
    answer = max(dp[-1])
    return answer