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())
fib = [None] * (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):
mod = 10 ** 9 + 7
mod2 = 2 ** 61 + 1
from collections import deque
import heapq
import time
from bisect import bisect_left, insort_left, bisect_right
import sys
import random
import itertools

input = sys.stdin.readline
_NUMINT_ALL = list(range(10))
_START_TIME = time.time()
INDEX_KETA = 10**12

def main():
    ans = solve()

    if ans is True or ans is False:
        YesNo(ans)
    elif ans is None:
        return

    if isinstance(ans, tuple):
        split_print_space(ans)
    else:
        print(ans)


def solve():

    n = iip()
    memo = [1, 1]

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

    print(memo[n])










def kiriage_warizan(a, b):
    return -(-a//b)


def iip(listed=False):  
    d = input().rstrip("\n").split()
    try:
        ret = [int(i) for i in d]
    except:
        ret = [int(i) if i in _NUMINT_ALL else i for i in d]
        if len(ret) == 1 and listed is False:
            return ret[0]

    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def iipt(l, listed=True, num_only=True):  
    if isinstance(l, list):
        l = l[0] 
    ret = []
    for i in range(l):
        ret.append(iip(listed=listed))
    return ret


def saidai_kouyakusuu(A):  
    l = len(A)
    while True:
        m = min(A)
        mx = max(A)
        if m == mx:
            return m

        for i in range(l):
            if A[i] % m == 0:
                A[i] = m
            else:
                A[i] %= m


def flatten(l):
    return list(itertools.chain.from_iterable(l))


def index_sorted(sorted_list, target):
    idx = bisect_left(sorted_list, target)
    if idx != len(sorted_list) and sorted_list[idx] == target:
        return idx
    else:
        return False


def time_debug_10percent():
    a = random.randint(0, 9)
    if a == 9:
        sys.exit()

def time_debug(t):
    time.sleep(_START_TIME + t - time.time())
    sys.exit()


def make_graph_edge_flat(N):  
    ret = []
    for i in range(N-1):
        a, b, c = iip()
        a -= 1
        b -= 1
        ret[a].append((b, c))
        ret[b].append((a, c))
    return ret


def sort_tuples(l, index):  
    if isinstance(l, list):
        l.sort(key=lambda x: x[index])
        return l
    else:
        l = list(l)
        return sorted(l, key=lambda x: x[index])


def count_elements(l):  
    d = {}
    for i in l:
        if i in d:
            d[i] += 1
        else:
            d[i] = 1
    return d


def safeget(l, index, default="exception"):  
    if index >= len(l):                      
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。配列の長さは", len(l), "です"]))
        else:
            return default
    elif index < 0:
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。負の値は許可されていません"]))
        else:
            return default
    else:
        return l[index]


def sortstr(s):  
    return "".join(sorted(s))


def iip_ord(startcode="a"):  
    if isinstance(startcode, str):
        startcode = ord(startcode)
    return [ord(i) - startcode for i in input()]


def YesNo(s):  
    if s:
        print("Yes")
    else:
        print("No")


def fprint(s):  
    for i in s:
        print(i)


def bitall(N):  
    ret = []
    for i in range(2 ** N):
        a = []
        for j in range(N):
            a.append(i % 2)
            i //= 2
        ret.append(a)
    return ret

def split_print_space(s):  
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):  
    print("\n".join([str(i) for i in s]))


def soinsuu_bunkai(n):  
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):  
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        
        pass
    return ret


def inv(n, mod):  
    return power(n, mod - 2)


def power(n, p, mod_=mod):  
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


def nibutan_func(func, target, left, right, side="left", seido = 1): 
    l = left
    r = right
    if seido == 1:
        x = (l + r) // 2
    else:
        x = (l + r) / 2
    while r-l > seido:
        
        if seido == 1:
            x = (l + r) // 2
        else:
            x = (l + r) / 2
        if func(x) == target:
            if side == "left":
                r=x
            else:
                l=x


        elif func(x) > target:
            r = x
        else:
            
            l = x

    
    if side == "left" and func(r) == target:
        return r
    elif side != "left" and func(l) == target:
        return l
    elif side == "left":
        return l
    else:
        return r


def nibutan_list(list_, target, side="left"):  
    if not isinstance(list_, list):
        list_ = list(list_)

    l = 0
    r = len(list_)
    x = (l + r) // 2
    while r-l > 1:
        x = (l+r)//2
        if list_[x] == target:
            return x
        elif list_[x] > target:
            r = x
        else:
            l = x

    if side == "left" or list_[x] == target:
        return l
    else:
        return r


class UfTree():
    def __init__(self, maxnum):
        self.parent = list(range(maxnum))
        self._size = [1] * maxnum
        self.rank = [0] * maxnum

    def size(self, a):
        return self._size[self.root(a)]

    def root(self, a):
        rank = 0
        cur = a
        while True:
            if self.parent[cur] == cur:
                
                
                return cur
            else:
                self.parent[cur] = self.parent[self.parent[cur]]
                cur = self.parent[cur]
                rank += 1

    def unite(self, a, b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb:
            return self

        self._size[ra] += self._size[rb]
        self.parent[rb] = ra
        return self

if __name__ == "__main__":
    main()

Solution (Python):
def makeFibonacci(n):
    F = [0] * (n+1)
    if n == 0:
        F[0] = 1
    else:
        F[0] = 1
        F[1] = 1
        for i in range(2, n+1):
            F[i] = F[i-2]+F[i-1]
    return F

n = int(input())
Ans = makeFibonacci(n)
print(Ans[n])

Solution (Python):
import math
import copy
import sys
import fractions


import decimal
import heapq
import collections
import itertools
import bisect



sys.setrecursionlimit(100001)







def getInputIntList():
    outputDataList = []
    inputData = input().split()
    outputDataList = [int(n) for n in inputData]

    return outputDataList


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList




n = int(input())

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

print(d[n])

Solution (Python):


DP = [-1 for i in range(45)]
DP[0] = 1
DP[1] = 1

def fib(i):
    if DP[i] != -1:
        return DP[i]
    else:
        DP[i] = fib(i-1) + fib(i-2)
        return DP[i]

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

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

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

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

Solution (Python):
class Fib:
    def __init__(self):
        self.memo = {0: 1, 1: 1}
    
    def calc_fib(self, n):
        if n in self.memo.keys():
            return self.memo[n]
        
        self.memo[n] = self.calc_fib(n - 2) + self.calc_fib(n - 1)
        return self.memo[n]
    
fib = Fib()
print(fib.calc_fib(int(input())))

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

print(fib[n])

Solution (Python):
def fib_memo(n):
    memo = [0] * (n + 1)

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

    return _fib(n)

N = int(input())
print(fib_memo(N))

Solution (Python):


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

    if n == 0 or n == 1:
        result = 1
    else:
        A = [1] * (n + 1)

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

        result = A[n]

    print(result)

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

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

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

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

print(L[n])

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

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

Solution (Python):
MAX = 10**5
fib = [0]*MAX

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

N = int(input())
print(fibonacci(N))

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

from collections import deque
sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  

def fib_memo(n):
    memo = [0] * (n+1)
    def fib(n):
        if n <= 1:
            return 1
        if memo[n] != 0:
            return memo[n]
        memo[n] = fib(n-1) + fib(n-2)
        return memo[n]
    return fib(n)
print(fib_memo(ni()))

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


def inpl():
    return list(map(int, input().split()))


def f(n):
    if n < 2:
        return 1
    ret = [0] * (n + 1)
    ret[0] = 1
    ret[1] = 1
    for i in range(2, n + 1):
        ret[i] = ret[i - 2] + ret[i - 1]
    return ret[n]


print(f(int(input())))

Solution (Python):

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


if __name__ == '__main__':
    main()

Solution (Python):


n = int(input())











dp = {}
dp[0] = 1
dp[1] = 1

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

print(dp[n])

Solution (Python):
def resolve():
    '''
    code here
    '''
    import sys

    sys.setrecursionlimit(100000000)
    N = int(input())

    memo = [0 for _ in range(N+1)]

    def fina(n):
        if n <= 1:
            memo[n] = 1
            return 1

        if memo[n] != 0:
            return memo[n]

        memo[n-1] = fina(n-1)
        memo[n-2] = fina(n-2)        
        memo[n] = memo[n-1] + memo[n-2]

        return memo[n]
    
    print(fina(N))



if __name__ == "__main__":
    resolve()

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

dp = [-1] * (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])

Solution (Python):
n = int(input())+1
dp = [1]*n
for i in range(n):
    if i<2:
        continue
    dp[i] = dp[i-1]+dp[i-2]
print(dp[n-1])

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

Solution (Python):
n= int(input())
if n <= 1:
  print(1)
  exit()
fib_ = [0]*(n+1)
fib_[0] = 1
fib_[1] = 1

def fib(n):
  if fib_[n] >= 1:
    return fib_[n]
  else:
    fib_[n] = fib(n-1)+fib(n-2)
    return fib(n-1)+fib(n-2)
print(fib(n))

Solution (Python):
import sys
sys.setrecursionlimit(15000)
n = int(input())

memo = {0:1,1:1}

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

print(fib(n))

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

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

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

for i in range(n+1):
    if i<=1:
        dp[i]=1
        continue

    dp[i]=dp[i-1]+dp[i-2]
print(dp[-1])

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

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

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

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


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


print(fib(n))

Solution (Python):

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

Solution (Python):





def resolve():
    N=int(input())

    
    dp = [float('inf') for _ in range(N+1)]
    dp[0] = 1
    dp[1]=1


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



resolve()

Solution (Python):
n=int(input())
memo=[0]*47
def fibo(x):
    if x==0 or x==1:
        return 1
    elif memo[x]!=0:
        return memo[x]
    else:
        tmp=fibo(x-1)+fibo(x-2)
        memo[x]=tmp
        return tmp
print(fibo(n))

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

Solution (Python):
import sys





n = int(input())

l = [1,1]

def f(i):
    global l
    if i <= 1:
        return 1
    else:
        return l[i-1] + l[i-2]

for i in range(2,n+1):
    l.append(f(i))

print(l[n])

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

fib = [0]*(n+1)

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

print(fib[n])

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

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

print(map[-1])

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

N = int(input())

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


print("%d"%(table[N]))

Solution (Python):
N = int(input())
dp = [0] * (N + 1)
if N == 0:
    print(0)
    exit()
if N == 1:
    print(1)
    exit()
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):
n = int(input())

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

print(fib[n])

Solution (Python):
a=[0]*100
a[0]=1
a[1]=1
a[2]=1
def fib(n):
    if a[n]!=0:
        return(a[n])
    elif a[n]==0:
        a[n]=(fib(n-1)+fib(n-2))
        return(a[n])
x=int(input())
print(fib(x+1))

Solution (Python):
def fib(n):
    global Fib
    if n <= 1:
        return 1
    elif Fib[n] != -1:
        return Fib[n]
    else:
        return fib(n-1) + fib(n-2)

def fib_eff(n):
    global Fib
    Fib[0] = 1
    Fib[1] = 1
    for i in range(2, n+1):
        Fib[i] = Fib[i-1] + Fib[i-2]

n = int(input())
Fib = [-1] * 45
fib_eff(n)
print(Fib[n])

Solution (Python):


fib = [-1 for _ in range(50)]
fib[0] = 1
fib[1] = 2

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

N = int(input())
print(fib[N - 1])

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[N])

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

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

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

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

print(fib(n))

Solution (Python):
def fib(n):
    F = {}
    F[0], F[1] = 1, 1

    if n == 1 or n == 0:
        return 1

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

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

Solution (Python):
if __name__ == '__main__':
    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])

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

    n=int(input())
    if n==0 or n==1:
      print(1)
      return 
      
    dp=[0]*(1+n)
    dp[0]=1
    dp[1]=1
    for i in range(n-1):
        dp[i+2]=dp[i+1]+dp[i]
    
    print(dp[-1])   
 
if __name__=='__main__':
    main()

Solution (Python):
def make_fibonacchi(n: int):
    
    res = {}
    
    res[0] = 1
    res[1] = 1
    
    if n == 0 or n == 1:
        return 1
    
    for i in range(2, n + 1):
        res[i] = res[i-1] + res[i-2]
    
    return res[n]


n = int(input())
print(make_fibonacchi(n))

Solution (Python):
import sys
import math
import fractions
import itertools
from collections import deque
import copy
import bisect

MOD = 10 ** 9 + 7
INF = 10 ** 18 + 7
input = lambda: sys.stdin.readline().strip()

fib_list = [-1 for _ in range(100)]


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


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

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

Solution (Python):
dp = [0]*100
dp[0] = 1
dp[1] = 1

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

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

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]

ans = dp[n]
print(ans)

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):
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])

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

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

n_L = [0] * 45

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

print(n_L[n])

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

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

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

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

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

Solution (Python):
def get_fibonacci_number(n):
    if n < 2:
        return 1
    if not fibonacci_numbers[str(n)]:
        fibonacci_numbers[str(n)] = get_fibonacci_number(n-1) + get_fibonacci_number(n-2)
    return fibonacci_numbers[str(n)]

if __name__ == "__main__":
    n = int(input())
    fibonacci_numbers = {str(i):None for i in range(45)}
    print(get_fibonacci_number(n))

Solution (Python):


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

Solution (Python):






def fibonacci(n) -> int:
    a = 0
    b = 1
    c = 0
    for i in range(1, n+1):
        c = a + b
        a = b
        b = c
    
    return c


def main():
    n = int(input())
    print(fibonacci(n))
    pass


if __name__ == "__main__":
    main()

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

memo = [0]*100000

def  fib(n):

    if n == 0 or n ==  1:
        memo[n] =1

    if memo[n] == 0:
        memo[n] = fib(n-2) + fib(n-1)
        return memo[n]
    else:
        return memo[n]



print(fib(a))

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 - 2] + l[i - 1]
    
    return l[n]

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

main()

Solution (Python):
n = int(input())
dp = {}
def fibonacci(n):
    if n == 0 or n == 1:
        return 1
    if n in dp:
        return dp[n]
    dp[n] = fibonacci(n-1) + fibonacci(n-2)
    return dp[n]
print(fibonacci(n))

Solution (Python):
def power(base,exp,op=lambda x,y:x*y,ie=1):
    res = ie
    while exp:
        if exp & 1:
            res = op(res,base)
        base = op(base,base)
        exp >>= 1
    return res

def fibonacci(n):
    I = [1,0,0,1]
    A = [1,1,1,0]
    mmul = lambda P,Q: [P[0]*Q[0]+P[1]*Q[2],P[0]*Q[1]+P[1]*Q[3],P[2]*Q[0]+P[3]*Q[2],P[2]*Q[1]+P[3]*Q[3]]
    return power(A,n+1,mmul,I)[2]

print(fibonacci(int(input())))

Solution (Python):
N = int(input())
dp = [ -1 for x in range(50)]
def fib(n):
    if n == 0 or n == 1:
        dp[n] = 1
        return dp[n]
    if dp[n] != -1:
        return dp[n]
    dp[n] = fib(n-1)+fib(n-2)
    return dp[n]
print(fib(N))

Solution (Python):
res = [1, 1]

n = int(input())

for i in range(n - 1):
    res.append(res[i] + res[i + 1])

print(res[n])

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

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


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

print(x[-1])

Solution (Python):
"""
ALDS1_10_A
簡単な動的計画法を使ってフィボナッチ数列を計算する
"""
def Fibo(num):
    List = [None]*45
    for i in range(num+1):
        if i == 0:
            List[0] = 1
        elif i == 1:
            List[1] = 1
        else:
            List[i] = List[i-1]+List[i-2]
    return List

n = int(input())

print(Fibo(n)[n])

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

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

print(f[n])

Solution (Python):
MAX_N = 44
_memo = [None for _ in range(MAX_N + 1)]
_memo [0] = _memo[1] = 1

def fibonacci(n):
    
    if _memo[n] is not None:
        return _memo[n]
    else:
        _memo[n] = fibonacci(n - 1) + fibonacci(n - 2)
        return _memo[n]

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

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


dp = [-1]*(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[-1])

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

Solution (Python):
def main():
    n = int(input())
    if n <= 1:
        print(1)
    else:
        fib_list = [1, 1] + [None] * (n - 1)
        for i in range(2, n + 1):
            fib_list[i] = fib_list[i - 1] + fib_list[i - 2]
        print(fib_list[n])


if __name__ == "__main__":
    main()

Solution (Python):



def make_fib(n):
    if n == 0 or n == 1: return 1
    if F[n] != -1: return F[n]
    else:
        F[n] = make_fib(n-1)+make_fib(n-2)
        return(F[n])

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

n = int(input())
F = [-1 for i in range(50)]
F[0] = F[1] = 1   
print(make_fib(n))

Solution (Python):
n=int(input())
s=[-1 for i in range(n+1)]

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

print(fib(n))

Solution (Python):



def fibonacci(n):
    if n == 0 or n == 1:
        F[n] = 1
        return F[n]
    elif F[n] != -1:
        return F[n]
    else:
        F[n] = fibonacci(n-1) + fibonacci(n-2)
        return F[n]
    

F = [-1] * 50
print(fibonacci(int(input())))

Solution (Python):
def fib_memo(n):
    memo = [-1]*(n+1)
    def fib(n):
        if n==0 or n==1:
            return 1
        if memo[n] != -1:
            return memo[n]
        memo[n] = fib(n-1) + fib(n-2)
        return memo[n]

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

Solution (Python):
class Fib:
    def __init__(self):
        self.FIB = [1, 1]

    def fib(self, n):
        if n < len(self.FIB):
            return self.FIB[n]
        else:
            self.FIB.append(self.fib(n-1) + self.fib(n-2))
            return self.FIB[n]


N = int(input())
f = Fib()
print(f.fib(N))

Solution (Python):
def make_fibonacci(n):
    F = []
    F.append(1)
    F.append(1)
    for i in range(2, n+1):
        F.append(F[i-2]+F[i-1])
    return F

n = int(input())
F = make_fibonacci(n)
print(F[n])

Solution (Python):
def fib(n: int, meolist: dict):
    if n == 0 or n == 1:
        meolist[n] = 1
        return 1
    elif n in meolist.keys():
        return meolist[n]
    
    meolist[n] = fib(n - 1, meolist) + fib(n - 2, meolist)
    return meolist[n]

if __name__ == '__main__':
    n = int(input())
    meolist = {}
    print(fib(n, meolist))

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



def fib_org(n):
    if n in (0, 1):
        return 1

    count = 3
    prevprev = 1
    prev = 2
    while count <= n:
        tmp = prevprev + prev
        prevprev = prev
        prev = tmp
        count += 1

    return prev



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








N = int(input())
F = [0 for i in range(N + 1)]


def fib_memo(n):
    if n == 0 or n == 1:
        F[n] = 1
    if F[n] != 0:
        return F[n]
    F[n] = fib_memo(n - 2) + fib_memo(n - 1)
    return F[n]





















print(fib_org(N))

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

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

main()

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

arr = [0] * 45

arr[0] = 1
arr[1] = 1

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

print(arr[num])

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

Solution (Python):

def fibonacci(n):
    global F

    if F[n] != -1:
        return F[n]
    elif n in [0, 1]:
        F[n] = 1
        return F[n]
    else:
        F[n] = fibonacci(n-1) + fibonacci(n-2)
        return F[n]


n = int(input())
F = [-1] * 45

print(fibonacci(n))

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

Solution (Python):

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


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

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[N])

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

Solution (Python):
dp = [None for _ in range(50)]

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

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

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

Solution (Python):




n = int(input())

dp = [-1]*(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[-1])

Solution (Python):
def main():
    N = int(input())
    done = [False for i in range(N + 1)]
    memo = [0 for i in range(N + 1)]

    def do_dp(n):
        if done[n]:
            return memo[n]
        if n == 0:
            return 1
        elif n == 1:
            return 1
        else:
            memo[n] = do_dp(n - 1) + do_dp(n - 2)
            done[n] = True
            return memo[n]
    
    print(do_dp(N))

if __name__ == '__main__':
    main()

Solution (Python):
A = [None] * (44 + 1)
A[0] = 1
A[1] = 1


def fibonacci(n: int) -> int:
	if A[n] == None:
		A[n] = fibonacci(n - 1) + fibonacci(n - 2)
	return A[n]


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

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

Solution (Python):

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

    pre = 1
    cur = 1

    for _ in range(n-1):
        tmp = cur
        cur = pre + cur
        pre = tmp

    print(cur)


if __name__ == '__main__':
    main()

Solution (Python):
Fib = [1,1]

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

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

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


F = [0] * (n + 1)

F[0] = 1
F[1] = 1

for i in range(2, len(F)):
    F[i] = F[i - 1] + F[i - 2]

print(F[n])

Solution (Python):
n = int(input())
hashMap = {}
def f(n):
    hashMap[0] = 1
    hashMap[1] = 1
    for i in range(2, n+1):
        hashMap[i] = hashMap[i-1]+hashMap[i-2]
    return hashMap[n]
print(f(n))

Solution (Python):
import sys
input = sys.stdin.readline
dp: list = [-1] * 50
def fib(n: int) -> int:
    if n == 0 or n == 1:
        dp[n] = 1
        return dp[n]
    elif dp[n] != -1:
        return dp[n]
    else:
        dp[n] = fib(n-1) + fib(n-2)
        return dp[n]

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

if __name__ == '__main__': main()

Solution (Python):
num = int(input())
fibtbl = [ 0 for x in range(50)]
fibtbl[0] = 1
fibtbl[1] = 1

def fib(n):
    global fitbl
    
    if n == 0:
        return 1
    if n == 1:
        return 1
    
    if fibtbl[n-1] != 0:
        p = fibtbl[n-1]
    else:
        p = fib(n-1)
    
    if fibtbl[n-2] != 0:
        pp = fibtbl[n-2]
    else:
        pp = fib(n-2)
    
    fibtbl[n] = p + pp
    return p + pp
    

print(fib(num))

Solution (Python):
def fibr(n):
    if arr[n] != 0:
        return arr[n]
    if n < 2:
        arr[n] = 1
    else:
        arr[n] = fibr(n-1) + fibr(n-2)
    return arr[n]

n = int(input())
arr = [0 for i in range(n+1)]
print(fibr(n))

Solution (Python):
N = int(input())
a, b = 1, 1
n = 0
while n <= N:
  if n > 1:
    a, b = b, a + b
  n += 1

print(b)

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