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:
#coding:utf-8
#1_10_A
def fibo(n, numbers):
    if n == 0 or n == 1:
        numbers[n] = 1
        return numbers[n]
    elif numbers[n]:
        return numbers[n]
    else:
        numbers[n] = fibo(n - 1, numbers) + fibo(n - 2, numbers)
        return numbers[n]

n = int(input())
fibonacci_numbers = [0 for i in range(n + 1)]
print(fibo(n, fibonacci_numbers))

Submission status: Accepted

Solution code:
F =[1,1] + [0 for i in range(44)]

n = int(input())

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

print(F[n])

Submission status: Accepted

Solution code:
def fib(n):
    F = {0:1, 1:1}
    def fibonacci(n):
        ans = F.get(n,-1)
        if ans > 0: return ans
        F[n] = fibonacci(n-1) + fibonacci(n-2)
        return F[n]
    return fibonacci(n)
        
if __name__=='__main__':
    print(fib(int(input())))

Submission status: Accepted

Solution code:
if __name__ == "__main__":
    n = input()
    F = []
    F.append(1)
    F.append(1)
    for i in range(2,n+1):
        F.append(F[i-1] + F[i-2])

    print(F[n])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

memo = ['' for i in xrange(45)]


def recursion(n):
    if n == 0 or n == 1:
        return 1

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


def memo_search(n):
    if memo[n] != '':
        return memo[n]
    else:
        if n == 0 or n == 1:
            memo[n] = 1
            return 1
        memo[n] = memo_search(n - 1) + memo_search(n - 2)
        return memo[n]

if __name__ == '__main__':
    n = input()
    # print recursion(n)
    print memo_search(n)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

memo = ['' for i in xrange(45)]
dp = [0 for i in xrange(45)]


# ?????°?????¨?¨??????????O(2^n)?????????
def recursion(n):
    if n == 0 or n == 1:
        return 1

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


# ?????¢??????????????°?¨??????????O(n)?????§????????§??????
def memo_search(n):
    if memo[n] != '':
        return memo[n]
    else:
        if n == 0 or n == 1:
            memo[n] = 1
            return 1
        memo[n] = memo_search(n - 1) + memo_search(n - 2)
        return memo[n]


# ???????¨?????????§????¨??????????O(n)??¨??????
def dynamic_programming(n):
    for i in xrange(n + 1):
        if i == 0 or i == 1:
            dp[i] = 1
        else:
            dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]


if __name__ == '__main__':
    n = input()
    # print recursion(n)
    # print memo_search(n)
    print dynamic_programming(n)

Submission status: Accepted

Solution code:
n = int(input())

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

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


print(fib[n])

Submission status: Accepted

Solution code:
def fib(memo,n):
    if n in memo:
        return memo[n]
    else:
        if n == 0:
            return 1
        elif n == 1:
            return 1
        else:
            memo[n] = fib(memo,n-1)+fib(memo,n-2)
            return memo[n]

memo = {}
n = int(raw_input())
print fib(memo,n)

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def fib(n):
    if n == 0 or n == 1:
        return 1
    if A[n] is not None:
        return A[n]
    A[n] = fib(n - 1) + fib(n - 2)
    return A[n]


A = [None] * (44 + 1)
n = int(input())
print(fib(n))

Submission status: Accepted

Solution code:
# -*- coding: utf_8 -*-

n = int(input()) + 1
arr = [-1] * n

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

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

print(arr[n - 1])

Submission status: Accepted

Solution code:
n=input()

fn_first=1
fn_second=1

if n >= 2:
    for x in xrange(n-1):
        tmp = fn_first
        fn_first = fn_first + fn_second
        fn_second = tmp

print fn_first

Submission status: Accepted

Solution code:


def fibonacciDP(i):
    if i == 0:
        return 1
    elif i == 1:
        return 1
    else:
        if dp[i-1] is None and dp[i-2] is None:
            dp[i-1] = fibonacciDP(i-1)
            dp[i-2] = fibonacciDP(i-2)
        elif dp[i-1] is None:
            dp[i-1] = fibonacciDP(i-1)
        elif dp[i-2] is None:
            dp[i-2] = fibonacciDP(i-2)

        return dp[i-1]+ dp[i-2]

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



n = int(input())
dp = [None]*n

print(fibonacciDP(n))

Submission status: Accepted

Solution code:
#coding:UTF-8
def FN(n):
    if n==0 or n==1:
        F[n]=1
        return F[n]
    if F[n]!=None:
        return F[n]
    F[n]=FN(n-1)+FN(n-2)
    return F[n]

if __name__=="__main__":
    n=int(input())
    F=[None]*(n+1)
    ans=FN(n)
    print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys


def fib_bad(n):
    if not n or n == 1:
        return 1
    return fib_bad(n - 2) + fib_bad(n - 1)


def fib_dp(n):
    fib_list[:1] = [1, 1]
    for i in range(2, n + 1):
        fib_list[i] = fib_list[i - 2] + fib_list[i - 1]
    return fib_list.pop()


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    index = int(_input[0])
    fib_list = [None] * index
    # print(fib_bad(index))
    print(fib_dp(index))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys


# def fib_bad(n):
#     if not n or n == 1:
#         return 1
#     return fib_bad(n - 2) + fib_bad(n - 1)


def fib_dp(n):
    fib_list[:1] = [1, 1]
    for i in range(2, n + 1):
        fib_list[i] = fib_list[i - 2] + fib_list[i - 1]
    return fib_list.pop()


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    index = int(_input[0])
    fib_list = [None] * index
    print(fib_dp(index))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys


# def fib_bad(n):
#     if not n or n == 1:
#         return 1
#     return fib_bad(n - 2) + fib_bad(n - 1)


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


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    index = int(_input[0])
    fib_list = [None] * index
    print(fib_dp(index))

Submission status: Accepted

Solution code:
class Fibonacci(object):
    memo = [1, 1]

    def get_nth(self, n):
        if n < len(Fibonacci.memo):
            return Fibonacci.memo[n]
        # print('fib({0}) not found'.format(n))
        for i in range(len(Fibonacci.memo), n+1):
            result = Fibonacci.memo[i-1] + Fibonacci.memo[i-2]
            Fibonacci.memo.append(result)
            # print('fib({0})={1} append'.format(i, result))
        return Fibonacci.memo[n]


if __name__ == '__main__':
    # ??????????????\???
    num = int(input())

    # ?????£??????????????°????¨????
    f = Fibonacci()
    result = f.get_nth(num)

    # ???????????????
    print('{0}'.format(result))

Submission status: Accepted

Solution code:
from functools import lru_cache


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


class Fibonacci(object):
    memo = [1, 1]

    def get_nth(self, n):
        if n < len(Fibonacci.memo):
            return Fibonacci.memo[n]
        # print('fib({0}) not found'.format(n))
        for i in range(len(Fibonacci.memo), n+1):
            result = Fibonacci.memo[i-1] + Fibonacci.memo[i-2]
            Fibonacci.memo.append(result)
            # print('fib({0})={1} append'.format(i, result))
        return Fibonacci.memo[n]


if __name__ == '__main__':
    # ??????????????\???
    num = int(input())

    # ?????£??????????????°????¨????
    #f = Fibonacci()
    #result = f.get_nth(num)
    result = fib(num+1)

    # ???????????????
    print('{0}'.format(result))

Submission status: Accepted

Solution code:
from functools import lru_cache


@lru_cache(maxsize=None)
def fib(n):
    """ http://docs.python.jp/3/library/functools.html """
    if n < 2:
        return n
    return fib(n-1) + fib(n-2)


class Fibonacci(object):
    memo = [1, 1]

    def get_nth(self, n):
        if n < len(Fibonacci.memo):
            return Fibonacci.memo[n]
        # print('fib({0}) not found'.format(n))
        for i in range(len(Fibonacci.memo), n+1):
            result = Fibonacci.memo[i-1] + Fibonacci.memo[i-2]
            Fibonacci.memo.append(result)
            # print('fib({0})={1} append'.format(i, result))
        return Fibonacci.memo[n]


if __name__ == '__main__':
    # ??????????????\???
    num = int(input())

    # ?????£??????????????°????¨????
    f = Fibonacci()
    result = f.get_nth(num)
    #result = fib(num+1)

    # ???????????????
    print('{0}'.format(result))

Submission status: Accepted

Solution code:
from functools import lru_cache


@lru_cache(maxsize=None)
def fib(n):
    """ http://docs.python.jp/3/library/functools.html """
    if n < 2:
        return n
    return fib(n-1) + fib(n-2)


class Fibonacci(object):
    memo = [1, 1]

    def get_nth(self, n):
        if n < len(Fibonacci.memo):
            return Fibonacci.memo[n]
        # print('fib({0}) not found'.format(n))
        for i in range(len(Fibonacci.memo), n+1):
            result = Fibonacci.memo[i-1] + Fibonacci.memo[i-2]
            Fibonacci.memo.append(result)
            # print('fib({0})={1} append'.format(i, result))
        return Fibonacci.memo[n]


if __name__ == '__main__':
    # ??????????????\???
    num = int(input())

    # ?????£??????????????°????¨????
    # f = Fibonacci()
    # result = f.get_nth(num)
    result = fib(num+1)

    # ???????????????
    print('{0}'.format(result))

Submission status: Accepted

Solution code:
def fibonacci(n):
    num1 = 1
    num2 = 1
    tmp = 1

    for i in range(1, n):
        tmp = num1 + num2
        num1 = num2
        num2 = tmp

    return tmp


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

Submission status: Accepted

Solution code:
# ???????¨?????????????????§£???
# ?????°?????¨?????¢??????????????¨???????????¢????????£???


def fibonacci(n):
    num1 = 1
    num2 = 1
    tmp = 1

    for i in range(1, n):
        tmp = num1 + num2
        num1 = num2
        num2 = tmp

    return tmp


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

Submission status: Accepted

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

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:
from functools import lru_cache

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

n = int(input())
ans = fib(n)

print(ans)

Submission status: Accepted

Solution code:
def fib(n):
    f0, f1 = 1, 1

    for i in range(n - 1):
        f1, f0 = f1 + f0, f1

    return f1

n = int(input())
ans = fib(n)

print(ans)

Submission status: Accepted

Solution code:
n = int(input())

first = 1
second = 1
for i in range(n-1):
    second, first = first + second, second
print(second)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def fib(n):
    if n == 0 or n == 1:
        ans[n] = 1
        return 1
    # ?????¢???????¨?????????????????´???§????????°?????????????????????
    if ans[n] != -1:
        return ans[n]

    ans[n] = fib(n-1) + fib(n-2)
    return ans[n]


N = int(input())
ans = [-1 for i in range(N+1)]
a = fib(N)
print(a)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def fibonacci(n, memo=None):
    if memo==None:
        memo = [None]*n
    if n<=1:
        return 1 
    else:
        if memo[n-2]==None:
            memo[n-2] = fibonacci(n-2, memo)
        if memo[n-1]==None:
            memo[n-1] = fibonacci(n-1, memo)
    return memo[n-1] + memo[n-2]

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
 
 
def main(n):
    lst = [1, 1]
    for i in range(2, n + 1):
        lst.append(lst[i - 2] + lst[i - 1])
    return lst[n]
 

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


def main(n):
    lst = [1, 1]
    for i in range(2, n + 1):
        lst.append(lst[i - 1] + lst[i - 2])
    return lst[n]


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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

def main():
    def _fibonacci(n,cache):
        if n in cache:
            return cache[n]

        elif n == 0 or n == 1:
            ret = 1
            cache[n] = ret
            return ret
        else:
            ret = _fibonacci(n - 1, cache) + _fibonacci(n - 2, cache)
            cache[n] = ret
            return ret

    N = int(raw_input())
    cache = {}
    return _fibonacci(N,cache)

print main()

Submission status: Accepted

Solution code:
def fib(n, fib_table):
    if n == 0 or n == 1:
        return 1
    if fib_table[n] != None:
        return fib_table[n]
    fib_table[n] = fib(n-1, fib_table) + fib(n-2, fib_table)
    return fib_table[n]

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

print(fib(n, fib_table))

Submission status: Accepted

Solution code:


def main():
    n = int(input())
    dp = [0] * 100
    dp[0] = 1
    dp[1] = 1
    for i in range(2, len(dp)):
        dp[i] = dp[i - 1] + dp[i - 2]
    print(dp[n])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def fibonacci(n):
    if n == 0 or n == 1:
        F[n] = 1
        return F[n]
    if F[n] is not None:
        return F[n]
    F[n] = fibonacci(n - 1) + fibonacci(n - 2)
    return F[n]


n = int(input())
F = [None]*(n + 1)
print(fibonacci(n))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
_fib = [None] * 45
_fib[0] = 1
_fib[1] = 1

def fib(n):
    if _fib[n] is None:
        _fib[n] = fib(n-1) + fib(n-2)
    return _fib[n]

_n = int(raw_input())
print(fib(_n))

Submission status: Accepted

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

n = int(input())
print(makeFibonacci(n))

Submission status: Accepted

Solution code:
N = 44
F = [0]*(N+1)

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

if __name__ == '__main__':
    n = int(raw_input())
    print(dynamic(n))

Submission status: Accepted

Solution code:
F = {}

def fib(n):
  global F
  if n < 0:
    print("error")
    exit()
  if n < 2:
    F[n] = 1
    return F[n]
#  F[n] = fib(n-1) + fib(n-2)
  F[n] = F[n-1] + F[n-2]
  return F[n]

n = int(input())
#print(fib(n))
#n = int(input())
#print(fib(n))
#fib(44)
for i in range(n+1):
  result = fib(i)
print(result)
#  print(F[i])

Submission status: Accepted

Solution code:
F = {}

def fib(n):
  global F
  if n < 0:
    print("error")
    exit()
  if n < 2:
    F[n] = 1
    return F[n]
  F[n] = F[n-1] + F[n-2]
  return F[n]

n = int(input())
for i in range(n+1):
  result = fib(i)
print(result)

Submission status: Accepted

Solution code:
#!/usr/bin/python

n = int(input())

def fib(n):
    l = list()
    l.append(1)
    l.append(1)

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

    return l[-1]

print(fib(n))

Submission status: Accepted

Solution code:
n = int(input())

memo = [0 for _ in range(45)]

def fib_memo(n):
    if memo[n] != 0:
        return memo[n]
    elif (n == 0) or (n == 1):
        return 1
    else:
        memo[n] = fib_memo(n-1) + fib_memo(n-2)
        return memo[n]
    
print(fib_memo(n))

Submission status: Accepted

Solution code:
n = int(input())

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def g(a,b,n):
    if n==0 or n==1: return a
    else: return g(a+b,a,n-1)
a,b=1,1
print(g(a,b,int(input())))

Submission status: Accepted

Solution code:
def g(a,b,n):
    if n==1:return a
    else:return g(a+b,a,n-1)
a,b=1,1
print(g(a,b,int(input())))

Submission status: Accepted

Solution code:
def g(a,b,n):
    if n==1:return a
    else:return g(a+b,a,n-1)
print(g(1,1,int(input())))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import sys
import re
import math
import itertools
import functools
import logging

logging.basicConfig(level=logging.DEBUG, format="DBG: %(message)s")

def dbg(msg, *args, **kwargs):
    logging.debug(msg, *args, **kwargs)

def fib(n):
    assert n >= 0

    f0 = 1
    f1 = 1

    if n == 0: return f0
    if n == 1: return f1

    for _ in range(n-1):
        f2 = f1 + f0
        f0 = f1
        f1 = f2

    return f2

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

    print(fib(n))

if __name__ == "__main__": main()

Submission status: Accepted

Solution code:
if __name__ == "__main__":
    n = int(input())
    F = [1, 1]
    for i in range(n-1):
        F.append(F[-2]+F[-1])
    print(F[n])

Submission status: Accepted

Solution code:
print([1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170][int(input())])

Submission status: Accepted

Solution code:
n = int(input().strip())
if n <= 1:
    print(1)
    raise SystemExit
prev1 = 1
prev2 = 1
for i in range(2, n+1):
    fib = prev2 + prev1
    prev2, prev1 = prev1, fib
print(fib)

Submission status: Accepted

Solution code:
# coding=utf-8

def fib(n):
    global fib_list
    if fib_list[n]:
        return fib_list[n]

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

n = int(input())
fib_list = [None for i in range(n+1)]
print(fib(n))

Submission status: Accepted

Solution code:
def main():
    n = input()
    F = [0]*(n+1)
    number = fibonacci(n,F)
    print number

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

if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
memo = {}

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

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(100000)

calculated = set([0, 1])
cal_fib = [0 for _ in range(45)]
cal_fib[0:2] = 1, 1

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

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

Submission status: Accepted

Solution code:
def main():
    """ ????????? """
    num = int(input().strip())
    F = []
    for n in range(num+1):
        if n < 2:
            F.append(1)
        else:
            F.append(F[n-1] + F[n-2])
    print (F[num])
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())

cache = {0: 1, 1: 1}
def fibonacci(n):
    if cache.get(n, None) is not None:
        return cache[n]
    cache[n] = fibonacci(n-1) + fibonacci(n-2)
    return cache[n]

print(fibonacci(n))

Submission status: Accepted

Solution code:
def fibonacci(n):
    a, b = 1, 1
    for i in range(n-1):
        a, b = b, a+b

    return b

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

Submission status: Accepted

Solution code:
# Aizu Problem ALDS_1_10_A: Fibonacci Number
#
import sys, math, os

# read input:
PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input.txt", "rt")


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:
target = int(input()) + 1
fib = [0 for n in range(target + 1)]
for i in range(target + 1):
    if i == 0:
        continue
    elif i == 1:
        fib[i] = 1
    else:
        fib[i] = fib[i - 1] + fib[i - 2]
print(fib[target])

Submission status: Accepted

Solution code:
def fibonacci(f, n):
    if n == 0 or n == 1:
        f[n] = 1
        return f[n]
    if f[n]:
        return f[n]
    f[n] = fibonacci(f, n - 2) + fibonacci(f, n - 1)
    return f[n]

n = int(input())
f = [None for i in range(n + 1)]
print(fibonacci(f, n))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    ans = solve1(n)
    print(ans)


def solve1(n):
    if n <= 1:
        return 1
    a, b = 1, 1

    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-


def memoize(proc):
    cache = {}

    def helper(*args, **kargs):
        if args not in cache:
            cache[args] = proc(*args, **kargs)
        return cache[args]

    return helper


@memoize
def fib(n):
    if n < 2:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)


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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


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

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

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

n = int(input())
print(fib_memo(n, memo))

Submission status: Accepted

Solution code:
from functools import lru_cache
counter = 0
@lru_cache(maxsize=1024)

def fib(n):
    global counter
    counter += 1
    if n in [0, 1]:
        return 1
    return fib(n - 1) + fib(n - 2)

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

Submission status: Accepted

Solution code:
from functools import lru_cache

@lru_cache(maxsize=1024)

def fib(n):
    if n in [0, 1]:
        return 1
    return fib(n - 1) + fib(n - 2)

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

Submission status: Accepted

Solution code:
n = int(raw_input())

dp = [1, 1]

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

print dp[n]

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


if __name__ == '__main__':

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

    def fibonacci(n):
        if n == 0 or n == 1:
            F[n] = 1
            return F[n]
        if F[n] is not None:
            return F[n]
        
        F[n] = fibonacci(n-2) + fibonacci(n-1)
        return F[n]

    print(fibonacci(n))

Submission status: Accepted

Solution code:
memo = [1, 1]

def fib(n):
    if (n < len(memo)):
        return memo[n]

    memo.append(fib(n-1) + fib(n-2))
    return memo[n]

N = int(input())
print(fib(N))

Submission status: Accepted

Solution code:
num = int(input())

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

print(fibonacci(num))

Submission status: Accepted

Solution code:
import sys
numbers = []
for line in sys.stdin:
	numbers.append(int(line))

k = []
k.append(1)
k.append(1)

def getFib(i, n):
    if i == n :
        print(k[-1])
        return
    k.append(int(k[i - 1]) + int(k[i - 2]))
    getFib(i + 1, n)

getFib(2, int(numbers[0])+1)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
f=[1,1]
for _ in range(2,45):f+=[sum(f[-2:])]
print(f[int(input())])

Submission status: Accepted

Solution code:
f=[1,1]
for _ in[0]*43:f+=[f[-2]+f[-1]]
print(f[int(input())])

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:
p,n=(1+5**.5)/2,int(input())+1
print(int((p**n-(1-p)**n)/5**.5))

Submission status: Accepted

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

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

print(fib(n))

Submission status: Accepted

Solution code:
n = int(input())

A = []
A.append(1)
A.append(1)

if n>1:
    for i in range(n-1):
        A.append(A[i]+A[i+1])

print(A[n])

Submission status: Accepted

Solution code:

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

def fib(n):
    global f
    for i in range(2,n+1):
        f[i] = f[i - 1] + f[i - 2]
        #print(i,f[i])
    return f[n]

if __name__ == "__main__":
    n = input()
    n = int(n)
    #print(type(n))
    print(fib(n))

Submission status: Accepted

Solution code:
fib_dic = {0:1, 1:1}
def fib(n):
    ans = fib_dic.get(n)
    if ans == None:
        fib_dic[n] = fib(n-1) + fib(n-2)
    return fib_dic[n]

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Fri May  4 20:13:10 2018
ALDS1_10_A
@author: maezawa
"""

fib_arr = [None for _ in range(45)]
fib_arr[0] = 1
fib_arr[1] = 1

def fib(n):
    if fib_arr[n] != None:
        return fib_arr[n]
    fib_arr[n] = fib(n-1)+fib(n-2)
    return fib_arr[n]
    
n = int(input())
print(fib(n))

Submission status: Accepted

Solution code:
MAXN = 45
fibs = [-1] * MAXN


def fib(n):
    """Returns n-th fibonacci number

    >>> fib(3)
    3
    >>> fib(10)
    89
    >>> fib(20)
    10946
    """
    if n == 0:
        return 1
    elif n == 1:
        return 1
    elif fibs[n] == -1: 
        fibs[n] = fib(n-1) + fib(n-2)

    return fibs[n]


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


if __name__ == '__main__':
    run()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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


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

    if F[n]:
        return F[n]

    F[n] = fib(n-2) + fib(n-1)
    return F[n]


def main():
    print(fib(N))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def fibonacci(i, num_list):
    if i == 0 or i == 1:
        num_list[i] = 1
    else:
        num_list[i] = num_list[i-2] + num_list[i-1]

n = int(input()) + 1
num_list = [0 for i in range(n)]
for i in range(n):
    fibonacci(i, num_list)
print(num_list[-1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
fibs = {0: 1, 1: 1}


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

    return fibs[n]


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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import functools


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


if __name__ == '__main__':
    n = int(input())
    print(fib(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:
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())
fib = []
fib.append(1)
fib.append(1)
for _ in range(n - 1):
    fib.append(fib[-2] + fib[-1])
print(fib[-1])

Submission status: Accepted

Solution code:
# coding=utf-8


def fib(number):
    if number == 0 or number == 1:
        return 1
    memo1 = 1
    memo2 = 1

    for i in range(number-1):
        memo1, memo2 = memo1+memo2, memo1
    return memo1


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

Submission status: Accepted

Solution code:
#coding:utf-8
n = int(input())
F = [False for i in range(n+1)]
def fib(n):
    if n == 0 or n == 1:
        F[n] = 1
        return 1
    if F[n]:
        return F[n]
    F[n] = fib(n-2) + fib(n-1)
    return F[n]

a = fib(n)
print(a)

Submission status: Accepted

Solution code:
import sys

n=input()
a,b = 0,1

for i in range(0,n):
    a,b = b,a+b;
print b

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin


def fibo(n):
    a, b = 1, 1
    while n:
        a, b = b, a + b
        n -= 1
    return a


print(fibo(int(stdin.readline())))

Submission status: Accepted

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