프로그래머스 정수 삼각형

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

전형적인 dp문제이다.

처음 문제에서 제시한 그림을 봤을때는 이 문제가 떠올랐다.
https://programmers.co.kr/learn/courses/30/lessons/68645

이 문제와 비슷하게 이차원 배열을 생성해야 겠다고 생각했다.
가장 먼저 일단 위에서 최댓값을 만드는 경로를 택하고 나온 값중 큰 값을 선택하면 된다.
그렇기 때문에 나오는 최댓값을 계속 더해가는 방식으로 택하고, 아래에서는 위에서 어떻게 계산하였는지 몰라도 이 값이 최댓값이다라는 것을 알기 때문에 이미 계산해 놓은 결과를 사용하는 동적계획법을 사용하는 것이다.

가장 왼쪽(j==0)인 경우에는 바로 위의 값을 더해야 한다.
가장 오른쪽(j == i)인 경우에는 왼쪽 위의 값을 더해야 한다.
나머지의 경우 왼쪽 위를 택할지, 바로 위를 택할지 더해서 큰 수를 택하며 된다.

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