[DP] Dynamic Programing

Dynamic Programing

• recursion + Memoization
• 단순 테이블 채우기가 아니라 memoization을 이용해서 recursion을 smart하게 하는 기법.

 

# 문제해결 절차

 

1. 문제를 정확하게 정의하기.
2. 정의된 문제에 대한 subproblem을 생각한 뒤 이를 이용해 reccurence relation을 세운다.
   1. A(i)를 해결하기 위해서 이전단위의 subproblem의 solution으로 현재 해결하고자하는 식을 논리적으로 구한다.
3. memoization을 이용하여 recurrence relation 계산
   • 중간 결과물들을 저장할 data structure을 고른다. 대개 n차원 array 사용.
   • Subproblem들간의 dependency를 확인한다. (보통 top-down | bottom-up)
     • top-down이 bottom-up보다 빠르다.
     • bottom-up이 top-down보다 직관적이다.
     • top-down으로 실행이 되는데 bottom-up으로 실행이 안된 적이 거의 드물다. 때문에 대개 bottom-up으로 진행한다.
   • dependency에 기반하여 subproblem들의 답을 구하는 순서를 정하기.

 

# 적용 문제

• 구간 합, LIS( Longest Increasing Subsquence), edit, distance, knapsack...

 

보통 최적화 문제나 경우의 수를 풀때 주로 이용한다.