# Dynamic Programming[3] - 동적프로그래밍의 조건

# 동적 계획법

1. 일반적으로 최적화문제(최단경로같은) 혹은 카운팅문제(이항계수같은)들에 적용이 된다.

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

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

 

# optimal substructure

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

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

 

# optimal substructure를 확인하는 질문

- 최적의 해의 일부분이 그부분에 대한 최적의 해인가?

- shortest-path 문제

- 순환식은 optimal substructure를 표현한다.