[Python] 정수 삼각형

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

 

---

 

dp는 그림이나 식 안 쓰면 모르겠다.. dp 문제는 일단 dp[i] 부터 쓰고 봄

이 문제는 식이나 그림 자체는 쉬운데 dp 테이블을 삼각형 모양으로 그릴지 정사각 격자로 그릴지 고민했다

그냥 정사각 격자로 그리면 해결되는 문제였다

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