Go: package main

/*
フィボナッチ数列
*/

import (
	"bufio"
	"bytes"
	"fmt"
	"log"
	"os"
	"strconv"
	"strings"
)

func fibWithMemo(n int, memo map[int]int) int {
	if n == 0 || n == 1 {
		return 1
	}
	if val, ok := memo[n]; ok {
		return val
	}
	memo[n] = fibWithMemo(n-1, memo) + fibWithMemo(n-2, memo)
	return memo[n]
}

func fib(n int) int {
	memo := make(map[int]int)
	return fibWithMemo(n, memo)
}

func main() {
	scanner := makeScanner(1024)
	n := eGetInt(scanner)
	fmt.Println(fib(n))
}

////////////////////////////////////////////////////////////////////////////////
// ライブラリ
////////////////////////////////////////////////////////////////////////////////
func makeScanner(maxByte int) *bufio.Scanner {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Buffer(make([]uint8, 0, 8192), maxByte)
	return scanner
}
func makeWordScanner() *bufio.Scanner {
	scanner := makeScanner(8192)
	scanner.Split(bufio.ScanWords)
	return scanner
}
func eGetLine(r *bufio.Scanner) string {
	if r.Scan() {
		return r.Text()
	}
	err := r.Err()
	if err != nil {
		log.Fatal(err)
	}
	// EOF
	return ""
}
func eGetInt(r *bufio.Scanner) int {
	line := eGetLine(r)
	return eAtoi(line)
}
func eGetFields(r *bufio.Scanner) []string {
	line := eGetLine(r)
	return strings.Fields(line)
}
func eGetInts(r *bufio.Scanner) []int {
	fields := eGetFields(r)
	ints := make([]int, len(fields))
	for i := 0; i < len(ints); i++ {
		ints[i] = eAtoi(fields[i])
	}
	return ints
}
func eGetChars(r *bufio.Scanner) []string {
	line := eGetLine(r)
	return strings.Split(line, "")
}
func eAtoi(s string) int {
	n, err := strconv.Atoi(s)
	if err != nil {
		log.Fatal(err)
	}
	return n
}

type ints []int

func (s ints) String() string {
	var buf bytes.Buffer
	buf.WriteString("[")
	sep := ""
	for _, v := range s {
		buf.WriteString(fmt.Sprintf("%s%d", sep, v))
		sep = ", "
	}
	buf.WriteString("]")
	return buf.String()
}

func reverse(a ints) ints {
	r := make(ints, len(a))
	for i := 0; i < len(a); i++ {
		r[i] = a[len(a)-1-i]
	}
	return r
}
func max(a ints) (int, bool) {
	if len(a) == 0 {
		return 0, false
	}
	m := a[0]
	for _, e := range a {
		if e > m {
			m = e
		}
	}
	return m, true
}
func min(a []int) int {
	m := a[0]
	for _, v := range a {
		if v < m {
			m = v
		}
	}
	return m
}

func sum(a ints) int {
	if len(a) == 0 {
		return 0
	}
	sum := 0
	for _, e := range a {
		sum += e
	}
	return sum
}
func find(n int, a ints) int {
	for i, v := range a {
		if n == v {
			return i
		}
	}
	return -1
}

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

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

Python: n = int(input())

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

Python: n = int(input())
n1 = 1
n2 = 1
result = 0
if n < 2:
    result = 1
else:
    for i in range(n-1):
        result = n1 + n2
        n2 = n1
        n1 = result
print(result)

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

Python: N = int(input())
A = [0]*(N+1)
if N == 0 or N == 1:
    print(1)
else:
    A[0] = 1
    A[1] = 1
    for i in range(2, N+1):
        A[i] = A[i-1] + A[i-2]
    print(A[N])

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   #n=0 t0 1 pre-registered
print(make_fib(n))

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()

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

Python: n = int(input())

dp = [0]*(45)
dp[0] = 1
dp[1] = 1
def fib(i):
    j = 2
    while j <= i:
        if j >= 2:
            dp[j] = dp[j-1] + dp[j-2]
        j += 1

fib(n)
print(dp[n])

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

Python: #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))

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

Python: #40 フィボナッチ数列 - Time Limit Exceeded

n = int(input())
a = 1
b = 1
c = []
c.append(a)     #リストcの最後にaの値を付加
c.append(b)     #リストcの最後にbの値を付加
       
for i in range(n):
        c.append(a+b)   #リストcの最後にa+bの値を付加
        d = b           
        b += a
        a = d
print(c[n])

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

Python: F_list = [1,1] + [None]*43

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


n = int(input())

print(fibo(n))

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

Python: n=int(input())

a=[1]*45


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

Python: # -*- 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))

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

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

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()

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

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

Python: def Fibonacci(n, a1, a2):
	if n<1 : return a1
	return Fibonacci(n-1,a1+a2,a1)

print( Fibonacci( int(input()), 1, 0 ) )

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

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

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

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

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

Python: num = int(input())

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

print(fibonacci(num))