Dynamic Programming

1. 전략: bottom-up approach

1) 문제의 가장 작은 단위부터 사용할 수 있는 반복문을 작성한다.

2) 가장 작은 문제부터 차례대로 풀어나간다.

3) 저장된 결과를 재사용한다.

3) divide and conquer와의 공통점

- 문제를 작게 쪼개서 해결한다.

4) divide and conquer와의 차이점

- DAC의 경우 top-down 형식이기 때문에 중복 계산이 여러 개 생겨날 수 있다.

- DP는 bottom-up 형식이기 때문에 중복 계산이 생기지 않는다.

 

2. 예시

- binomial coefficient

- Floyd's algorithm for shortest paths

- traveling salesperson problem

- chained matrix multiplication

- optimal binary search trees

- sequence alignment