백준 (ALGORITHM) – 피보나치 수 2 (2748)

by 

n = int(input())

dp = (0 for _ in range(n+1))
#(0,1,0,0,0)
dp(0) = 0
dp(1) = 1

def dynamic(n):
    for i in range(2, n+1):
        dp(i) = dp(i-1) + dp(i-2)
    return dp(n)

print(dynamic(n))

이것은 기본적인 dp 문제입니다.

피보나치 수를 재귀적으로 구현하면 배열 (i-2) + (i-1)에서 입력되는 i의 함수

계산하려면 재귀적으로 호출해야 합니다.

이는 매우 비효율적이며 얻어지는 값이 커질수록 더 오래 걸립니다.

'추천 관련글,

따라서 dp를 사용하여 값을 저장하고 계속 진행하면 시간이 단축됩니다.