프로그래머스[Python] - 정수 삼각형

문제

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

프로그래머스

풀이

코드를 보며 차근차근 생각해보면 쉽게 이해되는 DP 풀이이다.

너무 어렵게 접근할 필요가 없다.

def solution(triangle):
    answer=0
    h = len(triangle)
    dp = [[0]*h for _ in range(h)]
    # 첫번째 행
    dp[0][0] = triangle[0][0]
    # 2~마지막 행
    for i in range(1,h):
        for j in range(len(triangle[i])):
            if j==0:
                dp[i][j] = dp[i-1][j]+triangle[i][j]
            else:
                dp[i][j] = max(dp[i-1][j-1]+triangle[i][j], dp[i-1][j]+triangle[i][j])
    answer = max(dp[-1])
    return answer