알고리즘 8장
DAG 최장 경로
DAG 최장 경로는 위상 순서대로 정점을 처리하면서 들어온 최적값을 다음 정점으로 전파하는 DP입니다.
상태 변화
위상 DP
A
→
B
→
C
→
D
dp[A]
0
dp[B]
4
dp[C]
7
dp[D]
9
불변식
점검
topological order
모든 간선이 앞에서 뒤로 가는 처리 순서를 만듭니다.
dp[u]
u까지 도달한 최장 비용을 저장합니다.
transition
간선 u→v에 대해 dp[v]를 갱신합니다.
DAG 조건
사이클이 있으면 위상 순서가 없어 이 방식이 성립하지 않습니다.