def fib(n):
if n==0:
return 0
elif n==1:
return 1
else:
return fib(n-1)+fib(n-2)
n=int(input())
dp=[fib(i) for i in range(n+1)]
print(dp[n])
동일한 코드를 python3와 pypy3로 제출했다..ㅎ
재귀로 풀면 시간초과가 발생하는 것을 알 수 있었다.
n=int(input())
dp=[]
dp.append(0)
dp.append(1)
for i in range(2,n+1):
dp.append(dp[i-1]+dp[i-2])
print(dp[n])
접근 방법