[백준/파이썬] 2748 피보나치 수 2

https://www.acmicpc.net/problem/2748

---

알고리즘 분류

• 다이나믹프로그래밍

문제풀이

두 가지 방법으로 해결가능하다.

코드1 : 탑다운 방식(메모이제이션)
한 번 계산한 결과를 메모리 공간에 메모

코드2 : 바텀업 방식

소스코드

코드1

n=int(input())
d=[0]*(n+1)

def fibo(n):
    if n==0:
        return 0
    elif n==1:
        return 1

    if d[n]!=0:
        return d[n]
    d[n]=fibo(n-1)+fibo(n-2)
    return d[n]

print(fibo(n))

코드2

n=int(input())

d=[0]*(n+1)
d[0]=0
d[1]=1

for i in range(2,n+1):
    d[i]=d[i-1]+d[i-2]

print(d[n])