다이나믹 프로그래밍으로 동적 계획법이라고 한다.
해결해야할 문제를 작은 문제로 나눈 다음 작은 문제의 답을 얻고 저장한다.
그리고 그 작은 문제의 답을 필요할때마다 사용한다.
피보나치 수열을 예를 들면
f[n]=f[n-1]+f[n-2] 이고 f[1] , f[0] = 1 이다
f[5]를 구하고 싶으면 f[4]와 f[3]을 구해야하고 f[4]를 구하려면 f[3]과 f[2]를 구해야한다.
이것을 트리로 표현하면
이렇게 되는데 여기서 보면 f[1] 과 f[0]으로 구한 f[2]값은 3번이나 다시 사용한다.
DP알고리즘에서는 이 f[2]값을 기억해 필요할 때 재사용하는 것이다.
또 f[2] 값을 알면 f[3]의 값도 알게되고 f[3]의 값을 저장해 필요할 때 또 사용한다.
즉 피보나치 수열 f[5]에서는 왼쪽에 있는 f[1] , f[2] , f[3] , f[4]를 한번 씩만 구하면 f[5]를 구할 수 있다.
시간 복잡도를 따졌을땐 DFS방식으로 전체를 탐색하면 O(2^n)이지만 DP방식을 사용하면 O(n)으로 확 줄어든다.
