Dynammic Programming

Memoization vs Tabulation

• memoization은 top-down이며 필요한 subprobelm 만 풀지만, function call로 인한 overhead 가 발생한다.
• Tabulation는 bottom-up이며, recursion 에 수반되는 overhead가 없다

DP 예시

1. 피보나치 수열
   • 동일한 피보나치 수를 2번 계산하지 않도록 한다.
   • recursion 만으로 풀 경우 동일한 피보나치 수를 2번 이상 계산하는 경우가 생긴다. 따라서 계산한 값을 저장해 둔다. (Memoization)
   • 피보나치의 경우 bottom up 방식으로 풀어도 된다(bottom up 도 dp)
2. 이항 계수 : nCk
   • nCk = n-1Ck + n-1Ck-1
3. Rod Cutting Problem
   • rod의 길이와 partition에 해당하는 price가 주어졌을 때 optimal price를 구하는 문제이다.
   • 길이 N의 rod cutting problem은 이전 값들을 활용해 풀 수 있다.
   • $r_n = max_{1\leq i \leq n }(p_i+r_{n-i})$
4. Matrix Chain Multiplication
   • A : m by n, B: n by r ⇒ mrn 의 시간 복잡도
   • $m[i,j]$ : $A_iA_{i+1}...A_j$ 를 곱하는 최소곱셈 횟수
   • $m[i,j] = min_{i\leq k \leq j-1}(m[i,k]+m[k+1,j]+p_{i-1}p_kp_j)$