DP(Dynamic Programming: 동적 계획법)
- 복잡한 (큰)문제를 작은 문제로 나눈 후, 작은 문제ㅢ 해법을 조합해 큰 문제의 해답을 구하는 기법의 총칭.
동적 계획법으로 해결할 수 있는 문제는 다음과 같은 특징을 가짐
1. 최적 하위구조(Optimal substructrue)
- 큰 문제를 분할한 작은 문제의 최적 값이 큰 문제에서도 최적 값.
- Principle of optimality라고도 불림.
2. 중복 하위문제(Overlapping problems)
- 큰 문제의 해를 구하기 위해서, 작은 문제의 최적 해를 재사용.
- 여러 번의 재사용을 하기 때문에 일반적으로 테이블에 저장해 둠.
MDP에서 정의한 bellman 기대/최적 방정식은 두 가지 특성을 만족시킴. 즉, 우리는 DP를 활용해 Bellman 기대/최적 방정식의 해를 효율적으로 계산 할 수 있음.
