Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

Fibonacci Number

  Write a program which prints $n$-th fibonacci number for a given integer $n$. The $n$-th fibonacci number is defined by the following recursive formula:

\begin{equation*}
fib(n)= \left \{
\begin{array}{ll}
1　         &   (n = 0)          \\
1　         &  (n = 1) \\
fib(n - 1) + fib(n - 2)  & \\
\end{array}
\right.
\end{equation*}

Input

  An integer $n$ is given.

output

  Print the $n$-th fibonacci number in a line.

Constraints

$0 \leq n \leq 44$

Sample Input 1

3

Sample Output 1

3



Sample input:
3


Sample output:
3

Submission status: Accepted

Solution code:
from functools import lru_cache
@lru_cache(maxsize=None)

def Fib(n):
    if n==0:
        return 1
    elif n==1:
        return 1
    else:
        return Fib(n-1)+Fib(n-2)
n=int(input())
print(Fib(n))

Submission status: Accepted

Solution code:
N = int(input())
a = b = 1
while N:
    a, b = b, a+b
    N -= 1
print(a)

Submission status: Accepted

Solution code:
a=b=1
for _ in range(int(input())): a,b=b,a+b
print(a)

Submission status: Accepted

Solution code:
def mul(A,B):
    C=[[0]*len(B) for i in range(len(A[0]))]
    for i in range(len(A)):
        for j in range(len(B[0])):
            for k in range(len(B)):
                C[i][j]=(C[i][j]+A[i][k]*B[k][j])
    return C

def matpow(vec,n):
    B=[[0]*len(vec) for i in range(len(vec))]
    for i in range(len(vec)):
        B[i][i]=1
    while(n>0):
        if n&1:
            B=mul(B,vec)
        vec=mul(vec,vec)
        n>>=1
    return B

N=int(input())
vec=[[1,1],[1,0]]

vec=matpow(vec,N+1)
print(vec[1][0])

Submission status: Accepted

Solution code:
n=int(input())

a=1
b=1

while n:
    a,b=b,a+b
    n -=1
    
print(a)

Submission status: Accepted

Solution code:
n=int(input())

a=[None] * (n+1)
a[0] = 1
a[1] = 1

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

print(a[n])

Submission status: Accepted

Solution code:
####
n = int(input())
memo = [-1]*(n+10)
def fib(i):
    if i==0 or i == 1:
        return 1
    if memo[i] != -1:
        return memo[i]
    memo[i] = fib(i-1) + fib(i-2)
    return memo[i]
print(fib(n))

Submission status: Accepted

Solution code:
from functools import lru_cache
n = int(input())

@lru_cache(maxsize=None)


def fib(n):
    if n==0 or n==1:
        return 1
   
    else:
        return fib(n-1)+fib(n-2)
        
print(fib(n))

Submission status: Accepted

Solution code:
n = int(input())
F = [1]*50
for i in range(2,n+1):
    F[i] = F[i-1] + F[i-2]
print(F[n])

Submission status: Accepted

Solution code:
n = int(input())

fib = []
ans = 0
for i in range(n+1):
    if i == 0 or i == 1:
        ans = 1
        fib.append(ans)
    else:
        ans = fib[i-1] + fib[i-2]
        fib.append(ans)

print(ans)

Submission status: Accepted

Solution code:
A=[0 for i in range(45)]
A[0]=1
A[1]=1
for i in range(2,45):
    A[i]=A[i-1]+A[i-2]
B=int(input())
print(A[B])

Submission status: Accepted

Solution code:
N = int(input())
a = b = 1
while N:
    a, b = b, a+b
    N -= 1
print(a)

Submission status: Accepted

Solution code:
n=int(input())
if n==0 or n==1:
    print(1)
else:
    a=[]
    a.append(1)
    a.append(1)
    for i in range(2,n+1):
        m=a[i-2]+a[i-1]
        a.append(m)
    print(m)

Submission status: Accepted

Solution code:
n = int(input())
if n < 2:
    print(1)
else:
    a, b = 1, 1
    for k in range(n - 1):
        a, b = b, a + b
    print(b)

Submission status: Accepted

Solution code:
from functools import lru_cache


@lru_cache(maxsize=None)
def fibo(n):
    if n == 0 or n == 1:
        return 1

    return fibo(n - 1) + fibo(n - 2)


n = int(input())

print(fibo(n))

Submission status: Accepted

Solution code:
n = int(input())

dp = [0] * (n+10)
dp[0] = 1
dp[1] = 1

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

print(dp[n])

Submission status: Accepted

Solution code:
def fib(n):
    fib = [1,1]
    for i in range(2,n+1):
        fib.append(fib[i-2]+fib[i-1])
    return fib[n]
    
n=int(input())
print(fib(n))

Submission status: Accepted

Solution code:
x=int(input())
a=1
b=1
i=1
if x==0:
    print(1)
elif x==1:
    print(1)

else:
    while i<=x-1:
        c=a+b
        a=b
        b=c
        i+=1
    print(c)

Submission status: Accepted

Solution code:
def fibonacci(F,n):
    F[0] = 1
    F[1] = 1
    for i in range(2,n+1,1):
        F[i] = F[i-1] + F[i-2]
    return F[n]

def main():
    n = int(input())
    F  = [0]*(n+1)
    ans = fibonacci(F,n)
    return ans

print(main())

Submission status: Accepted

Solution code:
n = int(input())

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

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

print(dp[n])

Submission status: Accepted

Solution code:
n = int(input())
f = [0]*45

f[0] = f[1] = 1
for i in range(2, 45):
    f[i] = f[i-2] + f[i-1]

print(f[n])

Submission status: Accepted

Solution code:
a=1
b=1
list=[]
n=int(input())
list.append(a)
list.append(b)
for i in range(n):
  list.append(a+b)
  d=b
  b+=a
  a=d
print(list[n])

Submission status: Accepted

Solution code:
f=[None for i in range(45)]

def fib(n):
    if n==0 or n==1:
        if f[n] is None:
            f[n] = 1
        return 1
    else:
        if f[n-2] is not None:
            f_n_2 = f[n-2]
        else:
            f_n_2 = fib(n-2)
            f[n-2] = f_n_2
        if f[n-1] is not None:
            f_n_1 =  f[n-1]
        else:
            f_n_1 = fib(n-1)
            f[n-1] = f_n_1
        f[n] = f_n_1 + f_n_2
        return f[n]
n = int(input())
print(fib(n))

Submission status: Accepted

Solution code:
N=int(input())
a = b = 1
while N:
    a,b=b,a+b
    N-=1
print(a)

Submission status: Accepted

Solution code:
n=int(input())
a=1
b=1
i=0
while i<n:
    a,b=b,a+b
    i+=1
print(a)

Submission status: Accepted

Solution code:
from functools import lru_cache


@lru_cache(None)
def fibo(n: int):
    if n == 0 or n == 1:
        return 1
    else:
        return fibo(n - 1) + fibo(n - 2)


n = int(input())
print(fibo(n))

Submission status: Accepted

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

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

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

print(dp[n])

Submission status: Accepted

Solution code:
N = int(input())
x = [0]*(N+1)
def fibo(n):
    if n ==0 or n==1:
        return 1
    else:
        if x[n] != 0:
            return x[n]
        else:
            x[n] = fibo(n-1)+fibo(n-2)
            return x[n]
print(fibo(N))

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict, deque
from copy import deepcopy
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
    
def fib(num):
    d = defaultdict(int)
    d[0] = 1
    d[1] = 1
    if num <= 1:
        return d[num]
    else:
        for i in range(1,num):
            d[i+1] = d[i]+d[i-1]
        return d[num]
    
    
    
def main():
    num = I()
    print(fib(num))
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
X = [0]*45
def fib(n):
    while 1:
        if n ==0 or n==1:
            return 1
        else:
            if X[n] != 0:
                return X[n]
            else:
                X[n] =fib(n-1)+fib(n-2)
            return X[n]


print(fib(N))

Submission status: Accepted

Solution code:
n = int(input())
data = []
x = []

if n == 0:
    print('1')
data.append(1)
if n == 1:
    print('1')
data.append(1)

if n >= 2:
    for i in range(2, n+1):
    #print(sum(data[i-2:i+1]))
    #print(data[1])
    #data.append(data[i])
        x = sum(data[i-2:i+1])
        data.append(x)
    #print(i, x)
        i = i + 1
    print(x)

Submission status: Accepted

Solution code:
n = int(input())

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

print(f[n])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

m = [1, 1] + [None]*50

def fibonacci(n):
    if m[n-2]:
        pass
    else:
        fibonacci(n-2)
    if m[n-1]:
        pass
    else:
        fibonacci(n-1)

    m[n] = m[n-1] + m[n-2]

N = int(input())

fibonacci(44)
print(m[N])

Submission status: Accepted

Solution code:
from collections import deque
from enum import Enum
import sys
import math

BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001

table = [0] * 45

table[0] = 1
table[1] = 1

for i in range(2,45):
    table[i] = table[i-1]+table[i-2]


N = int(input())
print("%d"%(table[N]))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

def fibo(n):
    if n==0:
        return 1
    if n==1:
        return 1
    if memo[n] != 0:
        return memo[n]
    memo[n]=fibo(n-1)+fibo(n-2)
    return memo[n]
n=int(input())
memo=[0 for i in range(n+1)]

print(fibo(n))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

n = int(input())
F = [1]*50
for i in range(2, n+1):
    F[i] = F[i-1] + F[i-2]

print(F[n])

Submission status: Accepted

Solution code:
#(40)フィボナッチ数列
n=int(input())
def fib(n):
    a=1
    b=1
    for _ in range(n):
        a,b=b,a+b
    return a
print(fib(n))

Submission status: Accepted

Solution code:
def fib(n):
  if n==0 or n==1:
    return 1
  
  x=[1,1]
  for i in range(2,n+1):
    x.append(x[i-1]+x[i-2])

  return x[-1]

print(fib(int(input())))

Submission status: Accepted

Solution code:
a=int(input())
n=[0]*(a+1)
n[0]=1
n[1]=1
for i in range(2,a+1):
  n[i]=n[i-1]+n[i-2]
print(n[a])

Submission status: Accepted

Solution code:
n = int(input())
fib_ls = [0] * (n+1)
fib_ls[0], fib_ls[1] = 1,1
for i in range(2,n+1):
    fib_ls[i] = fib_ls[i-1] + fib_ls[i-2]
print(fib_ls[n])

Submission status: Accepted

Solution code:
n=int(input())
num=[1,1]
for i in range(43):
    b=(num[-2])+(num[-1])
    num.append(b)
print(num[(n)])

Submission status: Accepted

Solution code:
import sys
n = int(input())
if n < 2:
    print(1)
    sys.exit()
a, b = 1, 1
for i in range(n-1):
    c = a + b
    a = b
    b = c
print(c)

Submission status: Accepted

Solution code:
N=int(input())
D=[0]*(N+1)
D[0]=1
D[1]=1

for i in range(2,N+1):
    D[i]=D[i-1]+D[i-2]
print(D[N])

Submission status: Accepted

Solution code:
n = int(input())
fib = []
for i in range (n+1) :
    if i <= 1 :
        fib.append(1)
    else :
        fib.append(fib[i-2]+fib[i-1])
print(fib[n])

Submission status: Accepted

Solution code:
import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array

# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def fib(dp, n):
    if n == 0 or n == 1:
        dp[n] = 1
        return dp[n]
    if dp[n] != -1:
        return dp[n]
    dp[n] = fib(dp, n - 1) + fib(dp, n - 2)
    return dp[n]


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    fb = [-1] * (N + 1)
    print(fib(fb, N))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
a=b=1
for i in range(int(input())):
    a,b=b,a+b
print(a)

Submission status: Accepted

Solution code:
n = int(input())
a = b = 1
while n:
    a, b = b, a+b
    n -= 1
print(a)

Submission status: Accepted

Solution code:
n = int(input())
a = int(0)
b = int(1)

if n==1:
    A = b
elif n==2:
    A = 2
else:
    for i in range(n):
        a,b = b,a+b
        A = b

print(A)

Submission status: Accepted

Solution code:
def fib(n):
    if n == 0 or n == 1:
        return 1
    else:
        seq = [0 for _ in range(n+1)]
        seq[0], seq[1] = 1, 1
        for i in range(2,n+1):
            seq[i] = seq[i-1] + seq[i-2]
        return seq[n]

if __name__ == '__main__':
    print(fib(int(input())))

Submission status: Accepted

Solution code:
n = int(input())

def Fib(n):
    a, b = 0, 1
    if n == 0:
        return a + 1
    elif n == 1:
        return b
    else:
        for i in range(n):
            a, b = b, a + b
        return b

print(Fib(n))

Submission status: Accepted

Solution code:
N = int(input())
dp = [0]*50
for i in range(N+1):
    if i < 2:
        dp[i] = 1
    else:
        dp[i] = dp[i-1]+dp[i-2]
print(dp[N])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# 標準入力を取得
n = int(input())

# 求解処理
# dp[i+1]: フィボナッチ数列の第i項
dp = [0 for _ in range(n + 1)]

# 初期条件
dp[0] = 1
dp[1] = 1

for i in range(1, n):
    # DP漸化式
    dp[i + 1] = dp[i] + dp[i - 1]
ans = dp[n]

# 結果出力
print(ans)

Submission status: Accepted

Solution code:
a=1
b=1
c=[]
n = int(input())

c.append(a)
c.append(b)

for i in range(n-1):
            c.append(a+b)
            d=b
            b+=a
            a=d
            
print(c[n])

Submission status: Accepted

Solution code:
n = int(input())
a=b=1
while n:
    a,b=b,a+b
    n-=1
print(a)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    N = int(readline())
    dp = [0] * 47
    dp[0] = 1
    dp[1] = 1
    for i in range(2,N+1):
        dp[i] = dp[i-1] + dp[i-2]
    print(dp[N])



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
a=1
b=1
i=0
while i<n:
  a, b=b, a+b
  i+=1
print(a)

Submission status: Accepted

Solution code:
n = int(input())

dict = {0:1,1:1}

def fib(n):
    if n in dict.keys():
        return dict[n]
    else:
        dict[n] = fib(n-1) + fib(n-2)
        return dict[n]

print(fib(n))

Submission status: Accepted

Solution code:
n = int(input())

dp = [1]*45

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

print(dp[n])

Submission status: Accepted

Solution code:
n=int(input())
def func(n):
    fibonacci = [1,2]
    for i in range(2,n):
        fibonacci.append(fibonacci[i-2]+fibonacci[i-1])
    return fibonacci[n-1]
print(func(n))

Submission status: Accepted

Solution code:
n = int(input())
fib = [0]*(n+1)
fib[0] = 1
fib[1] = 1

if n<=1:
  print(fib[n])
  exit()
for i in range(2,n+1):
    fib[i] = fib[i-1]+fib[i-2]

print(fib[n])

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

n = int(input())
m = [1,1]
if n == 0:
    print(1)
elif n == 1:
    print(1)
else:
    for i in range(2, n+1):
        m.append( m[i-1] + m[i-2] )
    print(m.pop())

Submission status: Accepted

Solution code:
n=int(input())
MAX_N=n
X = [None] * (MAX_N + 1)
def f(n):
    if n==0:
        return 1
    if n==1:
        return 1
    if X[n]:
        return X[n]
    r=f(n-1)+f(n-2)
    X[n]=r
    return r
print(f(n))

Submission status: Accepted

Solution code:
n = int(input())
memo = [1]*(n+1)
for i in range(2, n+1):
    memo[i] = memo[i-1]+memo[i-2]
print(memo[n])

Submission status: Accepted

Solution code:
n = int(input())
a =[1,1]
if n < 2:
    pass
else:
    for i in range(2,n+1):
        a.append(a[i-1]+a[i-2])
    
print(a[n])

Submission status: Accepted

Solution code:
def fibn(n):
    fib = [1,1]
    for i in range(2,n+1):
        fib.append(fib[i-2] + fib[i-1])
    return fib[n]
    
n = int(input())
print(fibn(n))

Submission status: Accepted

Solution code:
fib=[0]*45
fib[0]=1
fib[1]=1

n=int(input())

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

Submission status: Accepted

Solution code:
N = int(input())

memolist = [-1]*(N+1)
def fib(x):
    if memolist[x] == -1:
        if x == 0 or x == 1:
            memolist[x] = 1
        else:
            memolist[x] = fib(x - 1) + fib(x - 2)
    return memolist[x]

print(fib(N))

Submission status: Accepted

Solution code:
f=[0]*45
f[0]=f[1]=1

def fib(n):
    if n ==0 or n==1:
        return 1
    else:
        if f[n] == 0:
            f[n] = fib(n-1)+fib(n-2)
            return f[n]
        else:
            return f[n-1]+f[n-2]
n = int(input())
print(fib(n))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def fib2(n):
    n0,n1 = 1,1
    ans = 1
    for i in range(2,n+1):
        n0,n1 = n1,ans
        ans = n0 + n1
    return ans

if __name__ == "__main__":
    n = int(input())
    print(fib2(n))

Submission status: Accepted

Solution code:
N = int(input())

one = 1
two = 1
for _ in range(1, N):
    three = one + two
    one, two = two, three
print(two)

Submission status: Accepted

Solution code:
n = int(input())
dp = [None for _ in range(n+1)]

def fib(i):
    if dp[i] is not None:
        return dp[i]
    if i==0:
        return 1
    if i==1:
        return 1
    dp[i] = fib(i-1) + fib(i-2)
    return dp[i]

print(fib(n))

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    fib = [1] * (n + 1)
    for i in range(2, n + 1):
        fib[i] = fib[i - 1] + fib[i - 2]
    print(fib[n])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n=int(input())
num=[1,1]
for i in range(43):
    b=(num[-2])+(num[-1])
    num.append(b)
print(num[(n)])

Submission status: Accepted

Solution code:
n = int(input())
p = [1,1]

if n <= 1:
    print (1)
    exit (0)

for i in range(2,n+1):
    p.append(p[i-2] + p[i-1])

print (p[n])

Submission status: Accepted

Solution code:
lis=[]
lis.append(1)
lis.append(1)
for i in range(2,45):
    lis.append(lis[i-1]+lis[i-2])

n = int(input())
print(lis[n])

Submission status: Accepted

Solution code:
a=[0]*45

def Fib(n):
    if n == 0:
        a[0]=1
        return 1
    elif n == 1:
        a[1]=1
        return 1
    else:
        if a[n]==0:
            a[n]=Fib(n-1)+Fib(n-2)
            return a[n]
        else:
            return a[n]
    
n=int(input())
print(Fib(n))

Submission status: Accepted

Solution code:
def fib(n,memo={}):
    if n==0 or n==1:
        return 1
    elif n in memo:
        return memo[n]
    else:
        memo[n]= fib(n-1,memo)+fib(n-2,memo)
        return memo[n]
n=int(input())
print(fib(n))

Submission status: Accepted

Solution code:
n = int(input())
F = [1]*50
for i in range(2, n+1):
    F[i] = F[i-1] + F[i-2]

print(F[n])

Submission status: Accepted

Solution code:
n = int(input())

d = {0:1,1:1}
def calc(n):
    if n not in d:
        d[n] = calc(n-2)+calc(n-1)
    return d[n]

for i in range(n):
    calc(i)

print(calc(n))

Submission status: Accepted

Solution code:
from functools import lru_cache

n = int(input())


@lru_cache(maxsize=None)
def rec(n):
    if n <= 1:
        return 1
    else:
        return rec(n - 1) + rec(n - 2)


print(rec(n))

Submission status: Accepted

Solution code:
def fib(n):
    a=[1,1]
    for i in range(2,n+1):
        a.append(a[i-2]+a[i-1])
        i+=1
    return a[-1]
    
n=int(input())
print(fib(n))

Submission status: Accepted

Solution code:
n = int(input())

dp = [0]*(n+1)

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

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

print(dp[n])

Submission status: Accepted

Solution code:
n=int(input())
fib=[1,1]
for i in range(2,n+1):
  fib.append(fib[-1]+fib[-2])
print(fib[-1])

Submission status: Accepted

Solution code:
n=int(input())

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

Submission status: Accepted

Solution code:
A=1
B=1
C=0 #２つ前の項
D=0 #1
N=int(input())
if N==0 or N==1:
    print(1)
elif N==2:
    print(2)

else:   
    C=B  #１
    D=A+B #2
    for i in range (N-3):
        B=C
        C=D
        D=B+C
    print(C+D)

Submission status: Accepted

Solution code:
N = int(input())
dp = {0:1,1:1}
for i in range(1,N):
    dp[i+1] = dp[i]+dp[i-1]
print(dp[N])

Submission status: Accepted

Solution code:
n = int(input())
dp = [0]*(n+1)
def fibo(n):
  if n <2:
    return 1
  if dp[n]  > 0:
    return dp[n]
  dp[n] = fibo(n-1) + fibo(n -2)
  return dp[n]
print(fibo(n))

Submission status: Accepted

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

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

print(dp[-1])

Submission status: Accepted

Solution code:
N=int(input())
L=[0 for i in range(N+1)]
L[0]=1
L[1]=1
for i in range(2,N+1):
    L[i]=L[i-1]+L[i-2]
print(L[N])

Submission status: Accepted

Solution code:
n=int(input())
a=b=1
for i in range(n):
    a,b=b,a+b
    n-=1
print(a)

Submission status: Accepted

Solution code:
a = int(input())
f1 = int(2)
f2 = int(1)
f = int(1)
if a == 1:
  print("1")
elif a == 2:
  print("2")
else:
  for b in range(2,a):
    f= f1+f2
    f2 = f1
    f1 = f
  print(f)

Submission status: Accepted

Solution code:

n=int(input())
f=[0]*45
def Fib(n):
    if n==0:
        return 1
    elif n==1:
        return 1
    else:
        if f[n]!=0:
            return f[n]
        else:
            f[n]=Fib(n-1)+Fib(n-2)
            return f[n]
print(Fib(n))

Submission status: Accepted

Solution code:
n=int(input())
if n == 1:
    print(1)
elif n == 2:
    print(2)
else:
    p=n+1 
    a=((1+5**(1/2))/2)**p
    b=((1-5**(1/2))/2)**p
    c=1/(5**(1/2))
    print(int(c*(a-b)))

Submission status: Accepted

Solution code:
def fib(n):
    global F
    if n not in F:
        F[n] = fib(n-1)+fib(n-2)
    return F[n]

F = {0:1,1:1}
print(fib(int(input())))

Submission status: Accepted

Solution code:
n=int(input())
def fib(n):
    a,b=1,1
    for i in range(n):
        a,b=b,a+b
    return a
print(fib(n))

Submission status: Accepted

Solution code:
n = int(input())
L = [-1]*(n+1)
def fib(i,L):
    if i <= 1:
        return 1
    else:
        if L[i] != -1:
            return L[i]
        else:
            L[i] = fib(i-1,L)+fib(i-2,L)
            return L[i]
        return fib(i-1,L)+fib(i-2,L)
print(fib(n,L))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    fib = [0] * (n + 1)
    fib[0], fib[1] = 1, 1
    for i in range(2, n + 1):
        fib[i] = fib[i - 1] + fib[i - 2]
    print(fib[-1])


if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

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

print(dp[n])

Submission status: Accepted

Solution code:
memo={}
def fib(n) :
    if n == 0 :
        return 1
    elif n == 1 :
        return 1
    else :
        if n-1 not in memo:
            memo[n-1] = fib(n-1)
        if n-2 not in memo:
            memo[n-2] = fib(n-2)
        return memo[n-1] + memo[n-2]
n = int(input())
print(fib(n))

Submission status: Accepted

Solution code:
def fibo(n):
    fibo = [1,1]
    for i in range(2,n+1):
        fibo.append(fibo[i-2]+fibo[i-1])
    return fibo[n]
    
n=int(input())
print(fibo(n))

Submission status: Accepted

Solution code:
n=int(input())
F=[None for i in range(n+1)]
F[0],F[1]=1,1
for i in range(2,n+1):
    F[i]=F[i-2]+F[i-1]

answer=F[n]
print(answer)

Submission status: Accepted

Solution code:
n=int(input())
a,b=1,1
if n<=1:
    print(1)
else:
    for i in range(n-1):
        c=a+b
        a=b
        b=c
    print(c)

Submission status: Accepted

Solution code:
n=int(input())
dp=[0]*(n+1)
dp[0],dp[1]=1,1
for i in range(2,n+1):
    dp[i]=dp[i-1]+dp[i-2]
print(dp[n])

Submission status: Accepted

Solution code:
N=int(input())
DP=[]
DP.append(1)
DP.append(1)
for i in range(2,N+1):
    DP.append(DP[i-1]+DP[i-2])
print(DP[N])

Submission status: Accepted

Solution code:
N=int(input())
DP=[0]*(N+1)
def fin(n):
    if DP[n]!=0:
        return DP[n]
    if n<=1:
        DP[n]=1
        return DP[n]
    else:
        DP[n]=fin(n-1)+fin(n-2)
        return DP[n]
print(fin(N))

Submission status: Accepted

Solution code:
_fib = [0] * 45

def fib(n):
    if n < 2:
        return 1
    if _fib[n] > 0:
        return _fib[n]
    _fib[n] = fib(n-1) + fib(n-2)
    return _fib[n]

n = int(input())
print(fib(n))

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


def main():
    n = int(input())

    fib = [1] * 46
    for i in range(2, 46):
        fib[i] = fib[i - 1] + fib[i - 2]

    ans = fib[n]
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n=int(input())
a=1
b=1
list=[]
list.append(a)
list.append(b)
for i in range(n):
  list.append(a+b)
  d=b
  b+=a
  a=d
print(list[n])

Submission status: Accepted

Solution code:
n = int(input())

fib = [0]*(n+1)
fib[0] = 1
fib[1] = 1

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

Submission status: Accepted

Solution code:
# 34

n = int(input())

dp = [None] * (n+1)
dp[0] = 1
dp[1] = 1

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

print(dp[n])

Submission status: Accepted

Solution code:
def fib(n):
    nums = []
    for i in range(n+1):
        if i <= 1:
            nums.append(1)
        else:
            nums.append(nums[i-1]+nums[i-2])
    return nums[n]


def main():
    n = int(input())
    print(fib(n))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())

dp = [0] * 45
dp[0], dp[1] = 1, 1

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

print(dp[n])

Submission status: Accepted

Solution code:
list=[1,1]
n=int(input())

t=0
sum=0
if n==0 or n==1:
    print(1)
else:
    for i in range(n):
        list.append(list[i]+list[i+1])
    print(list[n])

Submission status: Accepted

Solution code:
a=1
b=1
c=[]

n=int(input())
c.append(a)
c.append(b)
for i in range(n):
    c.append(a+b)
    d=b
    b+=a
    a=d
print(c[n])

Submission status: Accepted

Solution code:
n=int(input())
def func(n):
    fib=[1,1]
    for i in range(2,n):
        fib.append(fib[i-2]+fib[i-1])
    return fib[n-1]
print(func(n+1))

Submission status: Accepted

Solution code:
n = int(input())
pair = [1, 1]

for i in range(n - 1):
    pair[i % 2] = sum(pair)

print(pair[n % 2])

Submission status: Accepted

Solution code:
x = [1,1]
n = int(input())
for i in range(n):
    a=[x[i]+x[i+1]]
    x = x+a
print(x[n])

Submission status: Accepted

Solution code:
n=int(input())
a=1
b=1
mlist=[]
mlist.append(a)
mlist.append(b)
for i in range(n):
  mlist.append(a+b)
  d=b
  b+=a
  a=d
print(mlist[n])

Submission status: Accepted

Solution code:
def fib(n):
    if n==0 or n==1:
        return 1
    else:
        if f[n]!=0:
            return f[n]
        else:
            f[n]=fib(n-1)+fib(n-2)
            return f[n]
f=[0]*45
n=int(input())

print(fib(n))

Submission status: Accepted

Solution code:
n=int(input())
def fib(n):
    a=1
    b=1
    for _ in range(n):
        a,b=b,a+b
    return a
print(fib(n))

Submission status: Accepted

Solution code:
fib=[0]*45
fib[0]=1
fib[1]=1
for i in range(2,45):
    fib[i]=fib[i-1]+fib[i-2]

n=int(input())
print(fib[n])

Submission status: Accepted

Solution code:
n = int(input())
fib = [-1] * (n+1)
fib[0], fib[1] = 1, 1

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

print(fib[-1])

Submission status: Accepted

Solution code:
def fib(n):
    if n==0:
        return 1
    elif n==1:
        return 1
    else:
        a,b=1,2
        for i in range(n-2):
            a,b=b,a+b
        return b    

print(fib(int(input())))

Submission status: Accepted

Solution code:
n = int(input())
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
    if n == 0 or n == 1:
        return 1
    else:
        return fib(n-2)+fib(n-1)
print(fib(n))

Submission status: Accepted

Solution code:
n=int(input())
if n==0 or n==1:
    print(1)
else:
    N=1
    m=1
    for i in range(n-1):
        M=N+m
        m=N
        N=M
    print(M)

Submission status: Accepted

Solution code:
list=[1]*45

n=int(input())
def fib(n):
    if n==0 or n==1:
        return list[n]
    else:
        if list[n]==1:
            list[n]=fib(n-1)+fib(n-2)
            return list[n]
        else:
            return list[n]
      
print(fib(n))

Submission status: Accepted

Solution code:
n=int(input())
def fib(n):
     a=1
     b=1
     for _ in range(n):
          a,b=b,a+b
     return a
print(fib(n))

Submission status: Accepted

Solution code:
n = int(input())
def fib(n):
    m = [1,1]
    if n==0 or n==1:
        m=[1]
    else:
        for k in range(2,n+1):
            m.append(m[-1]+m[-2])
    return m

if n==0:
    l = fib(n)[n]
elif n==1:
    l = fib(n)[n-1]
else:
    l = fib(n)[n]
print(l)

Submission status: Accepted

Solution code:
n = int(input())
# dpテーブルの用意
dp = [-1]*(n+1)
# dpの初期値
dp[0], dp[1] = 1, 1

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

Submission status: Accepted

Solution code:
N = int(input())
dp = [1] * (N+1)
for i in range(2, N+1):
    dp[i] = dp[i-2] + dp[i-1]
print(dp[N])

Submission status: Accepted

Solution code:
N = int(input())
dp = [0]*(N+1)
dp[0] = 1
dp[1] = 1
for i in range(2, N+1):
    dp[i] = dp[i-1]+dp[i-2]
print(dp[-1])

Submission status: Accepted

Solution code:
a=1
b=1
c=[]
n=int(input())
c.append(a)
c.append(b)
for i in range(n):
    c.append(a+b)
    d=b
    b+=a
    a=d
print(c[n])

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(input())

dp = [0] * (N + 1)
dp[0] = 1
dp[1] = 1

def fib(n):
    if dp[n] > 0:
        return dp[n]
    
    dp[n] = fib(n - 1) + fib(n - 2)
    return dp[n]

print(fib(N))

Submission status: Accepted

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


def rec(x):
    if dp[x]>0:
        return dp[x]

    res=rec(x-1)+rec(x-2)
    dp[x]=res
    return dp[x]

print(rec(n))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

def fibo(n, memo = {}):
   if n == 0 or n == 1:
      return 1
   elif n in memo:
      return memo[n]
   else:
      memo[n] = fibo(n - 1, memo) + fibo(n - 2, memo)
      return memo[n]

n = int(input())
print(fibo(n))

Submission status: Accepted

Solution code:
n = int(input())

l = [1,1]

if n in [0,1]:
    print(1)
else:
    for i in range(2, n+1):
        fib = l[-1] + l[-2]
        l.append(fib)
    print(fib)

Submission status: Accepted

Solution code:
n=int(input())
x=1
y=1
a=0
for i in range(n):
    a=x
    x=y
    y=a+y
print(x)

Submission status: Accepted

Solution code:
a=1
b=1
list=[]
n=int(input())
list.append(a)
list.append(b)
for i in range(n):
    list.append(a+b)
    c=b
    b+=a
    a=c
print(list[n])

Submission status: Accepted

Solution code:
n=int(input())
a=1
b=1
if n==0 or n==1:
    print(1)
else:
    for i in range (n):
        a,b=b,a+b
    print(a)

Submission status: Accepted

Solution code:
n=int(input())
MAX_N=n
X = [None] * (MAX_N + 1)
def f(n):
    if n==0:
        return 1
    if n==1:
        return 1
    if X[n]:
        return X[n]
    r=f(n-1)+f(n-2)
    X[n]=r
    return r
    
print(f(n))

Submission status: Accepted

Solution code:
n = int(input())
dp = [0]*(n+1)
dp[0] = 1
dp[1] = 1
for i in range(2,n+1):
    dp[i] = dp[i-1] + dp[i-2]
print(dp[n])