[프로그래머스] 정수 삼각형 - 파이썬/DP

https://school.programmers.co.kr/learn/courses/30/lessons/43105

def solution(triangle):

    dp = []

    for i in range(1,len(triangle)+1):
        t = [0]*i
        dp.append(t)


    for i in range(len(triangle)):

        for j in range(i+1):
            if j==0: # 왼쪽 변일때
                dp[i][j] =dp[i-1][0] + triangle[i][0]
            elif j==i: # 오른쪽 변일때
                dp[i][j] =dp[i-1][j-1] + triangle[i][j]
            else: # 내부에 있을때
                dp[i][j] = max(dp[i-1][j-1],dp[i-1][j]) + triangle[i][j]

    answer = max(dp[-1])

    return answer

그림을 보면서 dp 배열을 채운뒤 마지막 층의 최대값을 구했다.