동적계획법(Dynamic programming)-3

동적계획법

1. 일반적으로 최적화문제(최소값,최대값) 혹은 카운팅 문제에 적용됨

2. 주어진 문제에 대한 순환식을 정의한다.

3. 순환힉을 memoization 혹은 bottom-up 방식으로 푼다.

- subproblem들을 풀어서 원래 문제를 푸는 방식, 그런 의미에서 분할정복법과 공통성이 있음

- 분할정복법에서는 분할된 문제들이 서로 disjoint하지만 동적계획법에서는 그렇지 않음

- 즉 서로 overlapping하는 subproblem들을 해결함으로써 원래 문제를 해결

분할정복법

동적계획법

Optimal Substructure

- 어떤 문제의 최적해가 그것의 subproblem들의 최적해로부터 효율적으로 구해질 수 있을 때 그 문제는 optimal substructure를 가진다고 말한다.

- 분할정복법/탐욕적기법/동적계획법은 모두 문제가 가진 이런 특성을 이용한다.

최장경로(Longest-Path) 문제

- 노드를 중복 방문하지 않고 가는 가장 긴 경로

- optimal substructure를 가지는가?