2를 8번 더하면 16이다. -> 2를 9번 더할 때는 다시 더하지 말고 2를 8번 더한 것에 2를 더하면 돼!
[https://hyunlee103.tistory.com/73]
위 그림을 코드로 구현해 봅시다.
#recursive
def fibonacci(x):
if x==0:
return 0
if x==1:
return 1
return fibonacci(x-1)+fibonacci(x-2)
fibonacci(8)
>>> 21
#dp
def fibonacci_dp(x):
dic = {}
dic[0] = 0
dic[1] = 1
for itr in range(2, x+1):
dic[itr] = dic[itr-2] + dic[itr-1]
return dic[x]
fibonacci_dp(8)
>>> 21
🧐정리
- dp를 사용하면 recursion과 달리 매 0,1 결과값으로 그 다음 스텝 값을 계속 저장한다.
- 여기서는 memoization table로 dictionary 자료구조를 이용했다.