Go: package main

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

func main() {
	sc1 := bufio.NewScanner(os.Stdin)
	sc1.Split(bufio.ScanWords)
	sc1.Scan()
	num, _ := strconv.Atoi(sc1.Text())
	cache := make([]*int, num+1)
	fmt.Println(fib(num, cache))

}

func fib(n int, cache []*int) int {
	if n <= 1 {
		return 1
	}

 	if cache[n] != nil {
		return *(cache[n])
	}

	result := fib(n -2, cache) + fib(n -1, cache)
	cache[n] = &result
	return result
}

C++: #include<iostream>

using namespace std;

long fivo(long req){
  long dp[100001];
  dp[0]=0;
  dp[1]=1;

  int i;
     for( i=2; i<req;i++){
       dp[i]=dp[i-1]+dp[i-2];
       //       cout <<dp[i]<<" "<<"="<<dp[i-1]<<"+"<<dp[i-2]<<endl;
     }
    dp[req]=dp[req-1]+dp[req-2];

     return dp[req];

}




int main(){
  long n;
  int req;

  cin >>req;
  n=fivo(req+1);
  //  for(n=1;n<=20;n++){
  //cout<<fivo(n)<<endl;
  // }
  cout <<n<<endl;
  return 0;
}

C++: #define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4244) // 最悪をします
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <numeric>
#include <queue>
#include <stack>
#include <map> 
#include <set>
#include <string>
#include <functional>
#include <list>
#include <random>
#include <time.h>
#include <iomanip>
#include <assert.h>
#include <numeric>
#include <sstream>
#define BIT(nr) (1UL << (nr))
#define int long long
//#define ll long long
#define double long double
#define mod 1000000007
#define MAXN (int)1e+5 * 2+1
#define LL_MAX 9223372036854775807	//ない環境用
#define LL_HALFMAX 9223372036854775807 / 2	//ない環境用
#define MIN -(9223372036854775807 / 2)
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
#define REPS(i,x) for(int i=1;i<=(int)(x);i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RREPS(i,x) for(int i=((int)(x));i>0;i--)
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define mp make_pair
template<typename T1, typename T2> inline void chmin(T1 & a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1& a, T2 b) { if (a < b) a = b; }


using namespace std;

//デバッグ用カッコの有無
#ifdef DEBUG
template <class T>ostream &operator<<(ostream &o, const vector<T>&v)
{
	o << "{"; for (int i = 0; i<(int)v.size(); i++)o << (i>0 ? ", " : "") << v[i]; o << "}"; return o;
}
#endif // DEBUG

template <class T>ostream &operator<<(ostream &o, const vector<T>&v)
{
	for (int i = 0; i<(int)v.size(); i++)o << (i>0 ? " " : "") << v[i]; return o;
}

int dx[4] = { 0, 1, 0, -1 }; // x軸方向への変位
int dy[4] = { 1, 0, -1, 0 }; // y軸方向への変位

int dxp[4] = { 0, 1 }; // x軸方向への変位(正のみ)
int dyp[4] = { 1, 0 }; // y軸方向への変位(負のみ)

using Weight = int;
using Flow = int;
struct Edge {
	int src, dst;

	// libalgo のものに追加、メンバを追加するだけなので互換性は崩さないはず、逆辺のG[e.dstの]インデックスを保持
	int rev;
	Weight weight;
	Flow cap;
	Edge() : src(0), dst(0), weight(0) {}
	Edge(int s, int d, Weight w) : src(s), dst(d), weight(w) {}
};
using Edges = std::vector<Edge>;
using Graph = std::vector<Edges>;
using Array = std::vector<Weight>;
using Matrix = std::vector<Array>;

void add_edge(Graph& g, int a, int b, Weight w = 1) {
	g[a].emplace_back(a, b, w);
	g[b].emplace_back(b, a, w);
}
void add_arc(Graph& g, int a, int b, Weight w = 1) { g[a].emplace_back(a, b, w); }

void solve() {

}

signed main() {
	int n;
	cin >> n;
	vector<int> dp(45, 0);
	dp[0] = dp[1] = 1;

	REP(i, 2, 45) {
		dp[i] = dp[i - 1] + dp[i - 2];
	}

	cout << dp[n] << "\n";
}

C++: #include<bits/stdc++.h>
using namespace std;


int main(){
  int n;
  cin >> n;
  vector<int> fib(n+1);
  
  if(n==0||n==1){
    cout << 1 << endl;
  }
  else{
  	fib[0] = 1;
  	fib[1] = 1;
  	for(int i=2;i<=n;i++){
    	fib[i] = fib[i-1] + fib[i-2];
    	//cout << fib[i+2] << endl;  
  	}
  	cout << fib[n] << endl;
  }
  
  return 0;
}

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

int fibans[44];
bool fibflag[44];

int fib(int n){
  if(n<2)return 1;
  if(fibflag[n] != true){
    fibans[n] = fib(n-1) + fib(n-2);
    fibflag[n] = true;
  }
  return fibans[n];
} 

int main(){
  int _n;
  cin >> _n;
  cout << fib(_n) << endl;
  return 0;
}

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

int main(){
  
  int n, fib[50] = {1, 1};

  //recurrence relation of fibonacci number
  for(int i = 2;i < 45;i++) fib[i] = fib[i - 1] + fib[i - 2];

  //input and output
  cin >> n;
  cout << fib[n] << endl;
  
  return 0;
}

C++: #include <iostream>

int FibonacciNumber(int Index)
{
	if(Index == 0) return 1;
	if(Index == 1) return 1;
	return FibonacciNumber(Index - 1) + FibonacciNumber(Index - 2);
}

int main()
{
	int Index;
	std::cin >> Index;
	std::cout << FibonacciNumber(Index) << std::endl;
	return 0;
}

C++: #include <bits/stdc++.h>
//----***やべーやつら***----
using namespace std;
#define int long long

//----***型定義***----
using ll = long long;
using P = pair<int,int>;

//----***Like a Pythonista***----
#define REP(ii,jj,nn) for (ll ii=jj;ii<(nn);ii++)
#define RREP(ii,nn,jj) for (ll ii = nn; jj<ii;ii--)
#define each(i,...) for (auto&& i:__VA_ARGS__)
#define ALL(vec) (vec).begin(),(vec).end()
#define sum(...) accumulate(ALL(__VA_ARGS__),0LL)
#define dsum(...) accumulate(ALL(__VA_ARGS__),0.0)
#define vec(type,name,...) vector<type> name(__VA_ARGS__)
template<class T> inline auto max(const T& a){ return *max_element(ALL(a)); }
template<class T> inline auto min(const T& a){ return *min_element(ALL(a)); }
inline ll gcd(ll a,ll b){if(b == 0) return a;return  gcd(b,a%b);}
inline ll lcm(ll a,ll b){ll g = gcd(a,b);return a / g * b;}

//----***定数***----
#define MOD 1000000007
#define INF 100000000000000000
#define EPS 1e-9
const vector<vector<int>> DXY={{-1,0},{1,0},{0,-1},{0,1}};

//----***パーツ***----
#define fr first
#define se second

//----***入出力***---
#define print(out) cout<< out  << "\n";
#define debug(var)  do{std::cerr << #var << " ↓ "<<"\n";view(var);}while(0);
#define dbg cerr<<"🥺🥺🥺🥺🥺🥺"<<endl;
template<typename T> void view(T e){std::cout << e << std::endl;}
template<typename T> void view(const std::vector<T>& v){for(const auto& e : v){ std::cout << e << " "; } std::cout << std::endl;}
template<typename T> void view(const std::vector<std::vector<T> >& vv){ for(const auto& v : vv){ view(v); } }

//----***初期時読み込み***----
struct initial{initial(){cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(15);};}initial_;

vector<int> memo(50,0);

int fibo(int n){
  if(memo[n]!=0){return memo[n];}
  memo[n]=fibo(n-1)+fibo(n-2);
  return memo[n];

}

signed main(){
  int N;cin>>N;
  memo[0]=memo[1]=1;
  int ans =fibo(N);
  print(ans)



}

C++: #include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define ll long long
using namespace std;

int dp[45];

int main(){
    int n;
    cin>>n;

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

    cout<<dp[n]<<endl;
    
    return 0;
}

C++: #include<iostream>
using namespace std;
#define MAX 45

int fib[45];
void make_fib(){
	fib[0] = 1;
	fib[1] = 1;
	for (int i=2;i<MAX;i++) {
	fib[i] = fib[i-1] + fib[i-2];
	}
}

int main() {
	int n;
	cin >> n;
	make_fib();
	cout << fib[n] << endl;
	return 0;
}

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


void fibonacci(int n){
  vector<int> fib;

  fib.push_back(1);
  fib.push_back(1);

  for(int i = 2;i < n;i++){
    fib.push_back(fib.at(i - 2) + fib.at(i - 1));
  }

  cout << fib.at(n - 1) << endl;

}

int main(){
  int n;
  cin >> n;
  fibonacci(n);

  return 0;
}