Problem:
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: 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

Solution (Python):
n = int(input())
  
def fibonacci(n):
  if n <= 1:
    dp[n] = 1
    return 1
  if dp[n] != -1:
    return dp[n]
  else:
    dp[n] = fibonacci(n-1)+fibonacci(n-2)
    return dp[n]
dp = [-1]*(n+1)
fibonacci(n)
print(dp[-1])

Solution (Python):
n = int(input())
n1 = 1
n2 = 1

for i in range(n):
    n1, n2 = n2, n1+n2

print(n1)

Solution (Python):
n = int(input())

fib=[]

fib.append(1)
fib.append(1)

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

print(fib[n])

Solution (Python):
fib = [0] * 45

fib[0] = fib[1] = 1

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

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

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

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

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

Solution (Python):
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])

Solution (Python):
n = int(input())

dp = [-1] * 100
dp[0] = 1
dp[1] = 1


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


if __name__ == "__main__":
    print(fib(n))

Solution (Python):
n=int(input())
a=[]
a.append(1)
a.append(1)

mamo =[-1]*100

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

print(a[n])

Solution (Python):
def fibonacchi(n: int) -> int:
    global computed_result
    if computed_result.get(n):
        return computed_result[n]
    else:
        computed_result[n] = fibonacchi(n - 2) + fibonacchi(n - 1)
        return computed_result[n]


if __name__ == "__main__":
    n = int(input())
    computed_result = {0 : 1, 1: 1}
    print(f"{fibonacchi(n)}")

Solution (Python):
import sys
m = int(input())
f = [0]*50
def fib(n):
  if n==0 or n==1:
    f[n] == 1
    return 1
  if f[n]!=0:
    return f[n]
  f[n] = fib(n-2) + fib(n-1)
  return f[n]

print(fib(m))

Solution (Python):
dp=[0]*50
dp[0]=1
dp[1]=1
N = int(input())

def makefib(n):
    if n == 0 or n == 1:
        return 1
    elif dp[n] == 0:
        dp[n] = makefib(n-1) + makefib(n-2)
        return dp[n]
    else:
        return dp[n]
print(makefib(N))

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

Solution (Python):
def fib(n, memo={}):
    if n == 0:
        return 1
    elif 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]


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


if __name__ == '__main__':
    main()

Solution (Python):
import sys
n=int(input())

if n<=1:
    print(1)
    sys.exit()
else:
    i=1
    a0=1
    a1=1
    while i<=n-1:
        temp=a1
        a1+=a0
        a0=temp
        i+=1
print(a1)

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

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

def calc(n):
    global dp
    for i in range(n+1):
        if i == 0:
            dp[i] = 1
        elif i == 1:
            dp[i] = 1
        else:
            dp[i] = dp[i-1] + dp[i-2]

def fibonacci(n):
    if n == 0:
        return 1
    if n == 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)


calc(n)
print(dp[n])

Solution (Python):

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


def main():
    print(fib(n))


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


if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = sys.stdin.readline

def fibo(i, dp):
	if dp[i] != -1:
		return dp[i]
	dp[i] = fibo(i-1, dp) + fibo(i-2, dp)
	return dp[i]

def main():
	n = int(input().strip())
	dp = [-1 for i in range(n+1)]
	dp[0] = 1
	dp[1] = 1
	print(fibo(n, dp))

if __name__ == '__main__':
	main()

Solution (Python):
N_MAX = 45 
F = [None] * N_MAX


def fibonacci(n):
    if n == 0 or n == 1:
        F[n] = 1
        return F[n]

    if F[n] != None:
        return F[n]

    F[n] = fibonacci(n - 1) + fibonacci(n - 2)

    return F[n]



n = int(input())
print(fibonacci(n))

Solution (Python):
n = int(input())

fib = [0] * 45

for i in range(len(fib)):
    if i == 0 or i == 1:
        fib[i] = 1
    else:
        fib[i] = fib[i-1] + fib[i-2]

    if i == n:
        print(fib[i])
        break

Solution (Python):
l = [0 for i in range(45)]
l[0] = 1
l[1] = 1
def F(n):
    if l[n] != 0:
        return l[n]
    else:
        l[n] = F(n-1) + F(n-2)
        return l[n]
print(F(int(input())))

Solution (Python):
n=int(input())
if n==0 or n==1:
    print(1)
else:
    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])

Solution (Python):
fib_table = [0 for _ in range(45)]
fib_table[0], fib_table[1] = 1, 1
for i in range(2, 45):
  fib_table[i] = fib_table[i-1]+fib_table[i-2]
n = int(input())
print(fib_table[n])

Solution (Python):
import sys
sys.setrecursionlimit(10**7)






mem = {}

def fib(n):
    if n == 0:
        return 1
    if n == 1:
        return 1
    if n not in mem.keys():
        res = fib(n-1) + fib(n-2)
        mem[n] = res
        return res
    else:
        return mem[n]

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

solve()

Solution (Python):
n = int(input())
fn0 = 1
fn1 = 1
if n == 0:
    fn = fn0
elif n == 1:
    fn = fn1
else:
    for ni in range(2, n+1):
        fn = fn0 + fn1
        fn0 = fn1
        fn1 = fn
print(fn)

Solution (Python):
n = int(input())
if n < 3:
    print(n)
else:
    n_1 = 1
    n_2 = 1
    for i in range(2, n+1):
        n_0 = n_1 + n_2
        n_2, n_1 = n_1, n_0
    print(n_0)

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

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

Solution (Python):
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])

Solution (Python):
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])

Solution (Python):
c=int(input())
a,b =1,1
while c-1:
    a,b=a+b,a;c -=1
print(a)

Solution (Python):
dp = {}


def fib(n):
    if n in dp:
        return dp[n]
    else:
        if n <= 1:
            dp[n] = 1
        else:
            dp[n] = fib(n-1) + fib(n-2)
        return dp[n]


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

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

Solution (Python):

"""
Created on Thu Mar 21 21:43:51 2019

@author: Yamazaki Kenichi
"""

s = int(input())










F = [1,1]
for i in range(s):
    F.append(F[-2]+F[-1])
print(F[s])

Solution (Python):
memo = {}


def f(n):
    if n == 0:
        return 1
    if n == 1:
        return 1

    a1 = memo.get(n - 1)
    if not a1:
        a1 = f(n - 1)
        memo[n - 1] = a1

    a2 = memo.get(n - 2)
    if not a2:
        a2 = f(n - 2)
        memo[n - 2] = a2

    return a1 + a2


n = int(input())
print(f(n))

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

Solution (Python):


def fib(a, b, c):
    if c==0:
        return a
    return fib(a+b, a, c-1)
    
n = int(input().rstrip())
print(fib(0, 1, n+1))

Solution (Python):
def fib(F, n):
    if n == 0:
        return 1    
    if n == 1:
        return 1
    else:
        F.append(fib(F, n-1) + F[n-2])
        return F[n]

n = int(input())
F = [1, 1]
ans = fib(F, n)
print(str(ans))

Solution (Python):
N = int(input())


def fibo(n, cache):
    cache[0] = 1
    cache[1] = 1
    for n in range(2, N+1):
        cache[n] = cache[n-1] + cache[n-2]
    return cache


print(fibo(N, [-1]*(N+1))[N])

Solution (Python):
n = int(input())

MAX = 45
table = [0] * MAX
for i in range(MAX):
    
    if i == 0 or i == 1:
        table[i] = 1
    else:
        table[i] = table[i - 1] + table[i - 2]

print(table[n])

Solution (Python):
n = int(input())
f1 = 1
f2 = 1
ans = 0
if n == 0 or n == 1:
    ans = 1
else:
    for i in range(n-1):
        if i%2 == 0:
            f1 = (f1 + f2)
            ans = f1
            
        else:
            f2 = (f1 + f2)
            ans = f2
            
print(ans)

Solution (Python):
dp = [0]*50

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

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

Solution (Python):
n = int(input())

for i in range(n+1):
    if i == 0 or i == 1:
        a = b = c = 1
    else:
        c = a + b
        a, b = b, c
print(c)

Solution (Python):
def fibonacci(F, n):
    if n == 0 or n == 1:
        F[n] = 1
        return F[n]
    if F[n]:
        return F[n]
    else:
        F[n] = fibonacci(F, n-1) + fibonacci(F, n-2)
        return F[n]

if __name__ == "__main__":
    n = int(input())
    F = []
    for _ in range(n+1):
        F.append(None)
    fibonacci(F, n)
    print(F[n])

Solution (Python):
n = int(input())

a0 = 1
a1 = 1

aList = [a0, a1]

if n == 0:
    print(a0)
    exit()
elif n == 1:
    print(a1)
    exit()
else:
    for i in range(2, n+1):
        aList.append(aList[i-1] + aList[i-2])

    print(aList[n])

Solution (Python):
fib = [0]*45
fib[0] = 1
fib[1] = 1
for i in range(2, 45):
    fib[i] = fib[i-1] + fib[i-2]
x = int(input())
print(fib[x])

Solution (Python):
n = int(input())
fib = [1, 1]

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

print(fib.pop())

Solution (Python):




class fibonacci:
    def __init__(self):
        self.result: List[int] = [-1]*1000
        return 
    def calc(self,n):
        if (n == 0 or n == 1):
            self.result[n] = 1
            return 1
        if (self.result[n] != -1):
            return self.result[n]
        self.result[n-1] = self.calc(n-1) 
        self.result[n-2] = self.calc(n-2)
        return self.result[n-1] + self.result[n-2]
n = int(input())

print (fibonacci().calc(n))

Solution (Python):
def fibonacci(n):
    if n <= 1:
        return 1
    fib_array = [1] * 45

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

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


main()

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

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

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

@lru_cache(maxsize=1000)
def fibo(n):
    if n < 2:
        return 1
    return fibo(n-1) + fibo(n-2)

print(fibo(n))

Solution (Python):
def fib(n):
    l = [0]*(n+1)
    l[0] = 1
    l[1] = 1
    for i in range(2, n+1):
        l[i] = l[i-1] + l[i-2]
    return l[n]

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

Solution (Python):
p = int(input())
def fib(n):
    dp = [0] * 50
    for i in range(n+1):
        if i == 0 or i == 1:
            dp[i] = 1
        else:
            dp[i] = dp[i-1] + dp[i-2]
    return dp[n]
print(fib(p))

Solution (Python):
memo = {} 
def fib(n):
  if n == 0 or 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]
print(fib(int(input())))

Solution (Python):
def fib(n):
    fib.cache = vars(fib).setdefault("cache", {})

    def f(n):
        if n <= 1:
            return 1
        else:
            return fib(n - 1) + fib(n - 2)

    if n not in fib.cache:
        fib.cache[n] = f(n)
    return fib.cache[n]


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


if __name__ == '__main__':
    main()

Solution (Python):


n = int(input())
F = [0] * (n + 1)


def fibonacci(n):
    global F
    if n == 0 or n == 1:
        F.append(1)
        F.append(1)
        return 1
    if F[n] != 0:
        return F[n]
    F[n] = fibonacci(n - 1) + fibonacci(n - 2)
    return F[n]


ans = fibonacci(n)
print(ans)

Solution (Python):
A = {}
def fibonacci(n):
    global A
    if n == 0 or n == 1:
        A[n] = 1
        return A[n]
    if n in A:
        return A[n]
    else:
        A[n] = fibonacci(n - 2) + fibonacci(n - 1)
        return A[n]

n = int(input())
print(fibonacci(n))

Solution (Python):
n=int(raw_input().strip())
a=1
b=1
if n<=1:
    print 1
else:
    for i in xrange(1,n):
        a,b=b,a+b
    print b

Solution (Python):
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]))

Solution (Python):
n = int(input())

dp = [0 for _ in range(45)]
dp[0], dp[1] = 1, 1


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

print(dp[n])

Solution (Python):
def fib_loop(a, t, n):
    if a < n:
        return fib_loop(a+1, (t[0]+t[1],t[0]), n)
    else:
        return t[0] + t[1]

def fib(n):
    if n < 2:
        return 1
    else:
        return fib_loop(2, (1,1), n)

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

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

    print(F[n])

Solution (Python):
n = int(input())
if n < 2:
	ans = 1
else:
	a = [0] * (n+1)
	a[0] = a[1] = 1
	for i in range(2, n+1):
		a[i] = a[i-1] + a[i-2]
	ans = a[n]
print(ans)

Solution (Python):
def calculate(nums):
    nums = nums.append(nums[-2] + nums[-1])
    return nums

n = int(input())
number_list = [0,1]

while True:
    if len(number_list) == n+2:
        print(number_list[-1])
        break
    else:
        calculate(number_list)

Solution (Python):
n = int(input())

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

print(fib[n])

Solution (Python):
memo = {}

def fib(n) :
    if n in memo.keys() :
        return memo[n]
    else :
        if n == 0 :
            return 1
        elif n == 1 :
            return 1 
        else :
            memo[n] = fib(n - 1) + fib(n - 2)
            return memo[n]
    
print(fib(int(input())))

Solution (Python):
class Fibonacci(object):
    record = [1, 1]
    
    def get_nth(self, n):
        if n < len(Fibonacci.record):
            return Fibonacci.record[n]
        
        for i in range(len(Fibonacci.record), n+1):
            result = Fibonacci.record[i-1] + Fibonacci.record[i-2]
            Fibonacci.record.append(result)
        
        return Fibonacci.record[n]
 
 
if __name__ == '__main__':
    num = int(input())
    f = Fibonacci()
    result = f.get_nth(num)
    print('{0}'.format(result))

Solution (Python):
class fibNum():
    def __init__(self):
        self.arr = [1, 1]
    def fib(self, n):
        return_num = 1
        if n > 1:
            if len(self.arr) <= n:
                self.arr.append( self.fib(n-1) + self.fib(n-2) )
            return_num = self.arr[n]
        return return_num

def main():
    n = int( input() )
    fn = fibNum()
    print( fn.fib(n) )

if __name__ == '__main__':
    main()

Solution (Python):
def fibonacci(n):
    a = [1]*2
    for i in range(2,n+1):
        a[0],a[1] = a[1],a[0]+a[1]
    return a[1]

n = int(input())
print(fibonacci(n))

Solution (Python):

memo={}
def fib(n):
    if n==0 or 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]

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

Solution (Python):

memo = [0]*45
for i in range(45):
    if i == 0 or i == 1:
        memo[i] = 1
    else:
        memo[i] = memo[i-1] + memo[i-2]
print(memo[int(input())])

Solution (Python):
a=[1,1]
def fib(n):
    try:
        return a[n]
    except:
        a.append(fib(n-2)+fib(n-1))
        return a[n]
n=int(input())
print(fib(n))