문제: 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
'Algorithm > Programmers' 카테고리의 다른 글
[코딩테스트 연습] 올바른 괄호의 갯수 (0) | 2020.07.24 |
---|---|
[코딩테스트 연습] 2 x n 타일링 (0) | 2020.07.22 |
[코딩테스트 연습] 베스트 앨범 (0) | 2020.07.14 |
[코딩테스트 연습]예산 (0) | 2020.07.10 |
[코딩테스트 연습]다리를 지나는 트럭 (0) | 2020.07.07 |