Dynamic Programming

Dynamic programming은 문제를 subproblems로 쪼개서 문제를 푸는 방식이다.

subproblem들이 독립적이면 divide-and-conquer 방식으로 풀 수 있고
독립적이지 않으면 dynamic programming을 한다.
독립적이지 않은 것의 의미는 sub problems가 subsub problems를 공유하는 것이다.
dynamic programming 알고리즘은 같은문제를 또 풀지 않기 위해서 subproblem을 한번만 풀고, 그 결과를 table에 저장한다. 그리고 나중에 필요할 때, 테이블을 참조해서 값을 가져온다.

 Dynamic programming은 최적화 문제(optimization problems)를 푸는데 이용된다.
솔루션은 여러개이지만 그중에 최적화 된 값(최소값 or 최대값)을 가진 솔루션은 하나다. Dynamic programming으로 그 솔루션을 찾는다.

문제 푸는 4가지 단계 
1. optimal substructure를 구한다.
2. recursive solution을 구한다. 
3. optimal solution의 값을 bottom-up 방식으로 계산한다.
4. 계산된 정보로 optimal solution을 구한다.

optimal solution의 sub solution도 optimal solution이다.

overlapping subproblems
순환적인 알고리즘이 같은 문제를 계속 반복하여 방문할 때.

참고 

cs.kangwon.ac.kr/~ysmoon/courses/2011_1/alg/06.pdf