[프로그래머스] 정수 삼각형(python 파이썬)

간단한 DP문제이다.

삼각형의 꼭대기에서 바닥까지 이어지는 경로중 합이 가장 큰값을 구한다.

n번째 줄의 i번째 숫자는

n-1번째 줄의 i-1, i 번째 숫자중 큰값과 해당 값을 더해서 구한다.

 

  

 

def solution(triangle):
    answer = 0
    l = len(triangle)
    dp = [[0] * l for _ in range(l)]
    
    dp[0][0] = triangle[0][0]
    
    for i in range(1, l):
        for j in range(0, i+1):
            if j == 0:
                dp[i][j] = dp[i-1][j] + triangle[i][j]
            elif j == i+1:
                dp[i][j] = dp[i-1][j] + triangle[i][j]
            else:
                dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]
        
                
    return max(dp[-1])