CS/Algorithm & Data Structure
[BOJ][Python]2748 피보나치 수2
Yeji Heo
2023. 5. 10. 13:01
재귀로 풀 수도 있겠지만 시간초과가 날 가능성으로 인해
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))