6. Dynamic Programming

동적 계획법을 알아보자.

6.1. Shortest paths in dags, revisited

방향 비순환그래프의 최단 경로들은 동적 계획법을 이용해 선형 시간에 풀 수 있다.

6.2. Longest increasing subsequences

최장 증가 부분순열은 동적 계획법을 이용해 $O(n \log n)$ 에 풀 수 있다.

6.3. Edit distance

단어의 수정 거리는 동적 계획법을 이용해 $O(mn)$ 에 풀 수 있다.

6.4. Knapsack

이산 배낭 문제는 O(nW)에 풀 수 있다. n에 대한 다항식으로 푸는 것은 불가능하다.

6.5. Chain matrix multiplication

최적의 행렬곱 순서 판정은 $O(n^{3})$ 에 풀 수 있다.

6.6. Shortest paths

All-pairs shortest paths

모든 쌍 최단 경로는 플로이드-와샬로 $O(V^{3})$ 에 풀 수 있으며 이도 동적 계획법의 일부이다.

The traveling salesman problem

순회하는 외판원 문제는 $O(n^{2} 2^{n})$ 에 풀 수 있다.

6.7. Independent sets in trees

트리 내 최대 독립적 집합의 수는 $O(V + E)$ 에 풀 수 있다.