Go: package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func getScanner(fp *os.File) *bufio.Scanner {
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 500001), 500000)
	return scanner
}

func getNextString(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}

func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}

func main() {
	fp := os.Stdin
	if len(os.Args) > 1 {
		fp, _ = os.Open(os.Args[1])
	}

	scanner := getScanner(fp)
	writer := bufio.NewWriter(os.Stdout)

	n := getNextInt(scanner)

	fmt.Fprintln(writer, fib(n))
	writer.Flush()

}

func fib(n int) int {
	if n <= 1 {
		return 1
	}
	dp := make([]int, n+1)
	dp[0] = 1
	dp[1] = 1
	for i := 2; i <= n; i++ {
		dp[i] = dp[i-2] + dp[i-1]
	}
	return dp[n]
}

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

Python: n=int(input())

dp=[1,1]
def fib(n):
    if n==0 and n==1:
        return dp[n]
    for i in range(2,n+1):
        dp.append(dp[i-1]+dp[i-2])
    return dp[n]
print(fib(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: #!/usr/bin/env python3
# -*- coding: utf-8 -*-

# https://qiita.com/e869120/items/eb50fdaece12be418faa
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_A&lang=ja


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


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


if __name__ == '__main__':
    main()

Python: def fib(n, fib_memo=None):                                                                                                                                                    
    if fib_memo == None:                                                                                                                                                      
        fib_memo = [None]*n                                                                                                                                                   
    if n <= 1:                                                                                                                                                                
        return 1                                                                                                                                                              
    else:                                                                                                                                                                     
        if fib_memo[n-1] == None:                                                                                                                                             
            fib_memo[n-1] = fib(n-1, fib_memo)                                                                                                                                
        if fib_memo[n-2] == None:                                                                                                                                             
            fib_memo[n-2] = fib(n-2, fib_memo)                                                                                                                                
        return fib_memo[n-1] + fib_memo[n-2]                                                                                                                                  
                                                                                                                                                                              
                                                                                                                                                                              
if __name__ == '__main__':                                                                                                                                                    
    n = input()                                                                                                                                                               
    print(fib(int(n)))

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

Python: N = int(input())

dp = [1] * (N + 1)

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

print(dp[N])

Python: _fib = [1, 1]

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

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

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

Python: n=int(input())

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

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

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

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

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

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

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

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

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

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

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

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

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)

#print(fibonacci(n))
calc(n)
print(dp[n])

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

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

Python: def fib(a, b, fiboli):
    if len(fiboli) < n:
        fiboli.append(a + b)
        fib(b, a + b, fiboli)
    else:
        print(fiboli[-1])

fibo_list = []
n = int(input())
fibo_list.append(n-2)
fibo_list.append(n-1)

fib(n - 2, n - 1, fibo_list)

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

Python: n = int(input())

F = [0]*50
F[0] = 1
F[1] = 1
if n== 0 or n==1:
    print(F[n])
else:
    for i in range(2,n+1):
        F[i] = F[i-1]+ F[i-2]
    print(F[n])

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