프로그래머스: 정수 삼각형

굉장히 전형적인 DP 문제

def solution(triangle):
    h = len(triangle)
    dp = [[] for _ in range(h)]
    dp[0].append(triangle[0][0])
    for i in range(1, h):
        dp[i].append(dp[i-1][0] + triangle[i][0])
        for j in range(1, i):
            dp[i].append(max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j])
        dp[i].append(dp[i-1][-1] + triangle[i][-1])
    return max(dp[h-1])