Go: package main

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

// main
func main() {
	//testFunction()
	solve(bufio.NewScanner(os.Stdin))
}

// test
func testFunction() {
	input := `
3
`
	sc := bufio.NewScanner(strings.NewReader(strings.Trim(input, "\n")))
	solve(sc)
}



func fib(n int, dp map[int]int) int {
	if n == 0 || n == 1 {
		return 1
	}
		if v, ok := dp[n]; ok {
		return v
	}
	r := fib(n - 1, dp) + fib(n - 2, dp)
	dp[n] = r
	return r
}

// solve
func solve(sc *bufio.Scanner) {
	sc.Split(bufio.ScanWords)
	sc.Scan()
	n, _ := strconv.Atoi(sc.Text())
	dp := make(map[int]int)
	r := fib(n, dp)
	fmt.Println(r)
}

C++: #include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<map>
#include<string.h>
#include<complex>
#include<math.h>
#include<queue>
#include <functional>
#include<time.h>
#include<iomanip>
using namespace std;
typedef long long int llint;
typedef pair<int, int> pint;
typedef pair<llint, llint> pllint;
typedef vector<int> vint;
typedef vector<llint> vllint;
typedef vector<pint> vpint;
typedef vector<string> vstring;
typedef vector<pair<llint, llint>> vpllint;
typedef vector<vector<int>> vvint;
typedef vector<vector<llint>> vvllint;
typedef vector<vector<pint>> vvpint;
typedef vector<bool> vbool;
typedef vector<vbool> vvbool;
#define rep(i,n) for(int i=0;i<n;i++)
#define drep(i,n) for(int i=n-1;0<=i;i--)
#define yes(ans) if(ans)cout<<"yes"<<endl;else cout<<"no"<<endl;
#define Yes(ans) if(ans)cout<<"Yes"<<endl;else cout<<"No"<<endl;
#define YES(ans) if(ans)cout<<"YES"<<endl;else cout<<"NO"<<endl;
#define POSSIBLE(ans) if(ans)cout<<"POSSIBLE"<<endl;else cout<<"IMPOSSIBLE"<<endl;
#define Pi 3.1415926535897932384626
#define mod llint(1e9+7)
#define Inf 2147483647
#define llInf 9223372036854775807
#define all(x) x.begin(),x.end()
#define pb push_back
#define isin(n,i) 0<=i&&i<n

class UnionFind {
public:
	//親の番号を格納する。親だった場合は-(その集合のサイズ)
	vector<int> Parent;

	//作るときはParentの値を全て-1にする
	//こうすると全てバラバラになる
	UnionFind(int N) {
		Parent = vector<int>(N, -1);
	}

	//Aがどのグループに属しているか調べる
	int root(int A) {
		if (Parent[A] < 0) return A;
		return Parent[A] = root(Parent[A]);
	}

	//自分のいるグループの頂点数を調べる
	int size(int A) {
		return -Parent[root(A)];//親をとってきたい
	}

	//AとBをくっ付ける
	bool connect(int A, int B) {
		//AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
		A = root(A);
		B = root(B);
		if (A == B) {
			//すでにくっついてるからくっ付けない
			return false;
		}

		//大きい方(A)に小さいほう(B)をくっ付けたい
		//大小が逆だったらひっくり返しちゃう。
		if (size(A) < size(B)) swap(A, B);

		//Aのサイズを更新する
		Parent[A] += Parent[B];
		//Bの親をAに変更する
		Parent[B] = A;

		return true;
	}
};

//セグ木・0-indexed・非再帰・(大きさ・単位元)で初期化
template<typename T>
struct SegTree {
	//比較関数の型
	using F = function<T(T, T)>;
	//二分木を配列で表したもの
	vector<T>seg;
	//木の半分の大きさ
	int siz;
	//単位元
	const T unit;
	//比較する関数
	const F f;

	//大きさn、unit(単位元)でsegtreeを初期化する
	SegTree(int n, const T unit, const F f) : unit(unit), f(f) {
		siz = 1;
		while (siz < n)siz <<= 1;
		seg.assign(siz * 2 - 1, unit);
		siz--;
	}

	//k番目にtを入力
	void set(int k, const T& t) {
		seg[k + siz] = t;
	}

	//fによって木を構築する
	void build() {
		for (int i = siz - 1; 0 <= i; i--) {
			seg[i] = f(seg[i * 2 + 1], seg[i * 2 + 2]);
		}
	}

	T operator[](const int i) {
		return seg[i + siz];
	}

	//k番目をxに更新する
	void update(int k, T x) {
		k += siz;
		seg[k] = x;
		while (0 < k) {
			k = (k - 1) >> 1;
			seg[k] = f(seg[k * 2 + 1], seg[k * 2 + 2]);
		}
	}

	//[a,b)について、fした結果を返す
	//半開区域のためa以上b未満の位置を指す
	T query(int a, int b) {
		T l = unit, r = unit;
		for (a += siz, b += siz; a < b; a >>= 1, b >>= 1) {
			if (!(a & 1))l = f(seg[a++], l);
			if (!(b & 1))r = f(seg[--b], r);
		}
		return f(l, r);
	}
};

//aとbの最大公約数を求めるよ
long long GCD(long long a, long long b) {
	if (b == 0) return a;
	else return GCD(b, a % b);
}

// 返り値: a と b の最大公約数
// ax + by = gcd(a, b) を満たす (x, y) が格納される
long long extGCD(long long a, long long b, long long& x, long long& y) {
	if (b == 0) {
		x = 1;
		y = 0;
		return a;
	}
	long long d = extGCD(b, a % b, y, x);
	y -= a / b * x;
	return d;
}

// mod. m での a の逆元 a^{-1} を計算する
long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}

//nCrを1000000007で割った余りを求める
llint nCr(llint n, llint r) {
	llint ans = 1;
	for (llint i = 0; i < r; i++) {
		ans *= n - i;
		ans %= 1000000007;
	}
	for (llint i = 1; i <= r; i++) {
		ans *= modinv(i, 1000000007);
		ans %= 1000000007;
	}
	return ans;
}

//aのb乗をmodで割った余りを求める
llint power(llint a, llint b) {
	if (b == 1)return a;
	if (b == 0)return 1;
	llint tmp = power(a, (llint)b / 2);
	tmp *= tmp;
	tmp %= mod;
	if (b % 2 == 1) {
		tmp *= a;
		tmp %= mod;
	}
	return tmp;
}

bool next_combination(llint& sub, int length) {
	llint x = sub & -sub, y = sub + x;
	sub = (((sub & ~y) / x) >> 1) | y;
	return sub < (llint)(1 << (llint)length);
}

vint memo(50, -1);

int f(int x) {
	if (memo[x] != -1)return memo[x];
	if (x == 0 || x == 1)return 1;
	else {
		return memo[x] = f(x - 2) + f(x - 1);
	}
}

int main() {
	int n;
	cin >> n;
	cout << f(n) << endl;
	return 0;
}

C++: #include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
using namespace std;
using ll = long long;
int INF = 1000000009;
int main()
{
    int n;
    cin >> n;
    ll fib[60];
    fib[0]=1;
    fib[1]=1;
    rep(i,n-1){
        fib[i + 2] = fib[i] + fib[i + 1];
    }
    cout << fib[n] << endl;
}

C++: #include <stdio.h> 
using namespace std;
 long long Fibonacci[43] = {0};
 long long fibo(int n){ 
if(n == 0) return 1;
 else if(n == 1) return 1; 
else{ if(Fibonacci[n-1] != 0 && Fibonacci[n-2] != 0){ 
//Do nothing }else if(Fibonacci[n-1] != 0){
 Fibonacci[n-2] = fibo(n-2); 
}
else if(Fibonacci[n-2] != 0){ 
Fibonacci[n-1] = fibo(n-1);
 }
else{ Fibonacci[n-1] = fibo(n-1);
 Fibonacci[n-2] = fibo(n-2); 
} 
return Fibonacci[n-1] + Fibonacci[n-2]; 
}
 } 

int main(){ int n; 
scanf("%d",&n);
 printf("%lld\n",fibo(n));

 }

C++: #include <iostream>
using namespace std;
int num;

int main(void) {
    cin >> num;
    int array[num] = {};
    array[0] = 1;
array[1] = 1;
    for (int i= 2; i <= num; i++) array[i] = array[i - 1] + array[i - 2];
    cout << array[num] << endl;
}

C++: #include <iostream>
using namespace std;
int fibonacci(int);
int dp[45];
int main(){
  int n,result,i;
  for(i=0;i<45;i++) dp[i]=0;
  cin >> n;
  result=fibonacci(n);
  cout << result << endl;
  return 0;
}
int fibonacci(int n){
  if(n==0||n==1) return dp[n]=1;
  if(dp[n]!=0) return dp[n];
  return dp[n]=fibonacci(n-1)+fibonacci(n-2);
}

C++: #include <cstdio>

int fibonacci(int n){
	if (n == 0 || n == 1){
		return 1;
	}
	else{
		return fibonacci(n-1) + fibonacci(n-2);
	}
}

int main(void){
	int n;
	scanf("%d", &n);
	printf("%d\n", fibonacci(n));
	return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;
#define MAX 44
int Fib[MAX];

// n番目のフィボナッチ数列を求める(再帰)
// int Calc_Fibonacci(int n1, int n2, int cnt)
// {
//     cnt--;
//     int n3 = n1 + n2;
//     if(cnt == 0) {
//         return n3;
//     } else {
//         return Calc_Fibonacci(n2, n3, cnt);
//     }
// }

int MakeFibonacci(int n)
{
    Fib[0] = Fib[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        Fib[i] = Fib[i-1] + Fib[i-2];
    }
    return Fib[n];
}

int main()
{
    int n = 0;
    int nRes = 0;

    scanf("%d",&n);
    // if (n==0 || n==1) {
    //     printf("1\n");
    // } else {
    //     nRes = Calc_Fibonacci(1, 1, n-1);
    //     printf("%d\n", nRes);        
    // }
    nRes = MakeFibonacci(n);
    printf("%d\n", nRes);  
}