DAG DP trust

DAG DP의 신뢰도는 네 증거로 나온다

값이 맞아 보이는지보다, 순서·초기값·전이·최종값이 각각 증명되는지가 중요하다.

01 순서topological order
02 초기값base state
03 전이edge direction
04 결과answer state
증거확인할 것오답 신호
순서부모 정점이 항상 자식보다 먼저 계산됨아직 안 채운 dp를 읽음
초기값source, terminal, empty 중 하나만 명확함문제 의미와 다른 0/1/INF
전이dp[v]가 dp[u]에서만 갱신됨역간선 또는 중복 경로 계산
결과답 정점 또는 전체 집계가 분리됨마지막 정점을 무조건 답으로 사용
핵심: DAG DP는 “순서가 증명된 반복문”이다. 순서 증거가 없으면 점화식도 믿을 수 없다.