[동적 계획법] 정수 삼각형

문제 설명

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

프로그래머스

문제 풀이

• 다이나믹 프로그래밍 문제
• 점화식: dp(i,j) = dp(i,j) + max( dp(i-1,j) , dp(i-1,j-1) ) 
• i,j의 기준을 아랫줄로 잡고 윗 줄에서 내려온 두 값 중 최댓값을 현재 위치에 더함

소스 코드(python)

def solution(triangle):
    answer = 0
    n = len(triangle)
    for i in range(n):    #밑에서 점화식을 계산할 때 j(세로)가 0번째 일때를 위해 맨 첫줄마다 0을 넣어줌
        triangle[i]=[0]+triangle[i]
    dp = [[0]*(n+1) for i in range(n)]
    for i in range(n):
        for j in range(1,i+2):
            dp[i][j]=triangle[i][j]
    for i in range(1,n):
        for j in range(1,i+2):
            dp[i][j] = dp[i][j] + max(dp[i-1][j],dp[i-1][j-1])

    return max(dp[n-1]) 	#맨 밑 줄 최댓값이 정답

if __name__=='__main__':
    t=[]
    for i in range(5):
        t.append(list(map(int,input().rsplit()))) 
    print(solution(t))