DP 다이나믹 프로그래밍

작은문제로 쪼개서 -> 값을 재활용하기

DP를 사용하면 재귀나 완전탐색보다 효율적으로 문제를 풀 수 있다

 

ex) 피보나치의 경우...

f(n) = f(n-1)+f(n-2) 

재귀 사용시 복잡도: O(n^2)

 

dp 사용시 복잡도: O(n)

 

 

dp를 사용할수 있는 조건

1. 큰 문제를 작은 문제들로 나눌 수 있는가(동일한 작은문제들이 반복)

2. 작은 부분 문제의 값이 그것을 포함하는 큰 문제에서도 동일한가

 

 

dp에서 중요한것 

- 점화식세우기

- memoization: 앞에서 계산한 값을 배열에 저장했다가 필요할 때 재사용

 

구현방법

top down

bottom up