백준 알고리즘 4150번 : 피보나치 수

링크

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

문제

피보나치 수열은 다음과 같이 그 전 두 항의 합으로 계산되는 수열이다. 첫 두 항은 1로 정의된다.

f(1) = 1, f(2) = 1, f(n > 2) = f(n − 1) + f(n − 2)

정수를 입력받아, 그에 해당하는 피보나치 수를 출력하는 프로그램을 작성하여라.

예제 입력 및 출력

풀이 코드(python)

n = int(input())

dp = [0 for i in range(10001)]

dp[0] = 0
dp[1] = 1
dp[2] = 1

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

print(dp[n])