작은 문제들의 답을 먼저 하고, 큰 문제를 이를 이용해 푼다 계산 결과를 적어 놓는 것과 비슷하다

Shortest Paths in DAG Problem

idea: 어떤 v로 도달하는 최소 경로는 edge(u,v)+dist(u)들중 최소이다 따라서 v를 계산하기 위해서 u를 사용 u는 또 다시 재귀적으로 edge(t,u)+dist(t)들중 최소… 이렇게 계산한다

이 예시에서 max로 바꾸면 최대 경로를 계산할 수 있다.

Longest Increasing Subsequences Problem

• input: seq of numbers $a_1, a_2, … , a_n$
• goal: find increasing subseq of max length

여기서는 2,3,6,9 또는 2,3,6,7이 되겠다.

어떻게 생각할 수 있을까? DAG의 path는 위상적으로 정렬 가능하므로 DAG로 생각 가능하며 모든 edge를 1이라 했을 때 최대 경로를 찾는 문제로 바뀌었다.

아래와 같은 알고리즘으로 동작한다.

(어디서든 출발해서) 1번 노드에 도달하는 최대 경로를 찾고

2번 노드까지 도달하는 최대 경로는 2번 노드로 올 수 있는 이전 노드들 중 가장 긴 경로를 따른다.

위 예시를 알고리즘으로 풀면 다음과 같을 것이다.

1. L(1) = 1 {5}