동적계획법(1)

[알고리즘] 동적계획법

• 동적 계획법은 큰 의미에서 분할 정복과 같은 접근방식을 의미한다.
• 메모이제이션(memoization): 함수의 결과를 저장하는 장소를 마련해 두고, 한 번 계산한 값을 저장해 뒀다 재활용하는 최적화 기법
• 대표적인 사용 방법:
1. 항상 기저 사례를 제일 먼저 처리. 접근을 벗어나는 등의 오류가 발생.
2. cache(이미 계산한 값을 저장해 두는 메모리의 장소)를 -1로 초기화. -1이 아닌 경우에는 계산이 된 경우가 아님을 의미.
3. ret는 cache[idx]의 참조형(reference)으로, 해당 값이 수정되면 ret 값도 수정되어 계산되었음을 의미.
4. 초기화하는 방법은  memset() 혹은 vector를 사용하여 초기화할 수 있음.
• 가장 유명한 예: 이항 계수(binomial co-efficient)
• 참고 문제: [PACKING] 여행짐싸기 http://yejin0730.tistory.com/1