Dynamic Programming 정리
in Algorithms
다음과 같은 특징을 가지면 dynamic programming으로 구현할 수 있다.
- Optimal Substructure (최적 부분 구조)
- 큰 문제를 작은 문제로 나눌 수 있다.
- Overlapping Subprobelm (중복되는 부분 문제)
- 동일한 작은 문제를 반복적으로 해결
Top Down (메모이제이션)
- 한번 계산한 결과를 메모리 공간에 메모한다.
- 캐싱이라고도 한다.
- 큰 문제를 해결하기 위해 작은 문제를 재귀적으로 호출해 ,그 문제가 해결됐을 때 큰 문제가 해결되게
Bottom Up
아래쪽에서 부터 작은 문제를 해결해 나가면서, 이 계산값을 사용해 다음 문제를 해결한다.
이게 다이나믹 프로그래밍의 전형적인 방식
i번째의 최적의 해는, i-1번째의 최적의 해와 i-2번째의 최적의 해를 비교해서 풀어나가는 경우가 많다.
a(i) = max(a(i-1),a(i-2)+ki)