다이나믹 프로그래밍 (DP)

 

recursive call 의 중간 결과를 저장하는 기법을 memorization (메모이제이션) 이라 하고 recursion 과 memorization 을 사용하여 문제를 해결하는 (알고리즘을 디자인 하는) 기법을 dynamic programming (DP)라고 한다

 

Dynamic programming = Recursion + Memoization

 

Dynamic programming 으로 문제를 해결하는 방법.

 

1.문제를 정확하게 정의하기.

 

2.정의된 문제에 대한 subproblem 을 정의한 뒤 (앞 예시에서는 subproblem = Fn’ (n’ < n) 구하기가 subproblem), subproblem 을 이용한 recurrence relation 을 세우기.

 

3.Memorization 을 이용하여 recurrence relation 계산

-중간 결과물들을 저장할 data structure 고르기 : 보통 n 차원 array 사용.

-Subproblem 들 간의 dependency 확인 (예 : Fn 을 구하려면 어떤 subproblem의 답들을 계산해 놓아야 하는가?)

-Dependency 에 기반하여 subproblem 들의 답을 구하는 순서를 정하기.

 

4.Time complexity 분석 및 알고리즘 작성.