[코딩테스트 연습] 정수 삼각형

 

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

---

DP 문제입니다. 점화식은 아래와 같습니다.

dp[h][w] 정의: 꼭대기부터 triangle[h][w] 칸까지 이어지는 경로의 합 중 최댓값.

//점화식
dp[h][w] = triangle[h][w] + max(dp[h-1][w-1], dp[h-1][w])

 

N제한이 크지않으므로 위와 같이 점화식을 세운 후

TOP-DOWN이나 BOTTOM-UP 방식 중 편한 걸로 풀면됩니다.

---

코드: https://github.com/cottory/algorithm/blob/master/PROGRAMMERS/PG43105.cc