[BOJ][Python]2748 피보나치 수2

재귀로 풀 수도 있겠지만 시간초과가 날 가능성으로 인해

DP 활용

 

1. Bottom-Up

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

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

print(dp[n])

2. Top-Down

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

DP[0] = 0
DP[1] = 1

def fib(num):
  if num==0 or num==1: return DP[num]
  elif DP[num]==0: DP[num]=fib(num-1)+fib(num-2)

  return DP[num]

print(fib(n))