Go: package main

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

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	n, err := nextInt(sc)
	if err != nil {
		panic(err)
	}
	fmt.Println(fibonacci(n, make(map[int]int)))
}

func fibonacci(x int, memo map[int]int) int {
	if x == 0 || x == 1 {
		return 1
	}
	if y, ok := memo[x]; ok {
		return y
	}
	z := fibonacci(x-1, memo) + fibonacci(x-2, memo)
	memo[x] = z
	return z
}

func nextInt(sc *bufio.Scanner) (int, error) {
	sc.Scan()
	return strconv.Atoi(sc.Text())
}

C++: #include <iostream>
#include<algorithm>
#include<stack>
#include<string>
#include<cstdlib>
#include<stdio.h>
using namespace std;
int n,a[50];
int solve(int i){
    if(i==1||i==0)return 1;
    return solve(i-1)+solve(i-2);
}
int main(){
    int n;
    cin>>n;
    cout<<solve(n)<<endl;
    return 0;
}

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

constexpr int inf = 1e9;
constexpr ll linf = 1e18;

template <typename T>
class Matrix
{
public:
    Matrix(int n, int m)
        : m_value(n, vector<T>(m, 0)), m_row(n), m_col(m) {}
    Matrix(initializer_list<initializer_list<T>> init)
        : m_value(init.begin(), init.end()), m_row(init.size()), m_col((*init.begin()).size()) {}

    int row(void) const { return m_row; }
    int col(void) const { return m_col; }

    vector<T> &operator[](int i) { return m_value[i]; }
    const vector<T> &operator[](int i) const { return m_value[i]; }

    // 単位行列E
    static Matrix E(int n)
    {
        Matrix res(n, n);
        for (int i = 0; i < n; i++) res[i][i] = 1;
        return res;
    }

    Matrix &operator+=(const Matrix &A)
    {
        int n = this->row(), m = this->col();
        assert(n == A.row() && m == A.col());

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                (*this)[i][j] += A[i][j];
            }
        } 
        return *this;
    }

    Matrix &operator-=(const Matrix &A)
    {
        int n = this->row(), m = this->col();
        assert(n == A.row() && m == A.col());

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                (*this)[i][j] -= A[i][j];
            }
        } 
        return *this;
    }

    Matrix &operator*=(const Matrix &A)
    {
        int n = this->row(), m = this->col(), l = A.col();
        assert(m == A.row());

        Matrix res(n, l);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < l; j++) {
                for (int k = 0; k < m; k++) {
                    res[i][j] += (*this)[i][k] * A[k][j];
                }
            }
        }
        return *this = move(res);
    }

    Matrix operator+(const Matrix &A) const { return Matrix(*this) += A; }
    Matrix operator-(const Matrix &A) const { return Matrix(*this) -= A; }
    Matrix operator*(const Matrix &A) const { return Matrix(*this) *= A; }

    Matrix pow(ll n) const
    {
        Matrix e = *this, res = E(this->row());
        while (n) {
            if (n & 1) res *= e;
            e *= e;
            n >>= 1;
        }
        return res;
    }

    friend ostream &operator<<(ostream &os, const Matrix &A)
    {
        int n = A.row(), m = A.col();
        for (int i = 0; i < n; i++) {
            os << "[";
            for (int j = 0; j < m; j++) {
                os << A[i][j];
                if (j < m - 1) os << ", ";
            }
            os << "]";
            if (i < n - 1) os << endl;
        }
        return os;
    }

private:
    vector<vector<T>> m_value;
    size_t m_row;
    size_t m_col;
};

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n; cin >> n;
    Matrix<ll> A = {{1, 1}, {1, 0}};
    A = A.pow(n);
    cout << A[1][0] + A[1][1] << endl;
    return 0;
}

C++: using namespace std;

int dp[44];

int fib(int n) {
	if (dp[n] != -1)return dp[n];
	int res;

	if (n == 0 || n == 1) {
		res = 1;
	}
	else {
		res = fib(n - 1) + fib(n - 2);
	}

	dp[n] = res;
	return res;
}

int main() {
	for (int i = 0; i < 44; i++) {
		dp[i] = -1;
	}
	int n;
	cin >> n;
	cout << fib(n);

	return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for (int i = 0; i < n; i++)
typedef long long ll;
// Welcome to my source code!

int F[45] = {};

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

int main() {
    int n;
    cin >> n;
    cout << fibonacci(n) << endl;
}

C++: // -*- mode:c++; coding:utf-8; c-basic-offset:2; -*-
// ALDS1_10_A: Fibonacci Number

#include <algorithm>
#include <cstdio>

#define NDEBUG
#include <cassert>

class Fibonnacci {
  static const unsigned int N = 44u;
  unsigned int n_;
  unsigned long* f_;

public:
  Fibonnacci(unsigned int n = N) : n_(std::max(1u, n))
  {
    f_ = new unsigned long[n_+1];
    f_[0] = f_[1] = 1;
    for (auto i = 2u; i <= n_; ++i) {
      f_[i] = f_[i-1] + f_[i-2];
    }
  }

  ~Fibonnacci() { delete[] f_; }
  
  unsigned long operator () (unsigned int n) const
  {
    assert(n <= n_);
    return f_[n];
  }
};

int main()
{
  unsigned int n;
  std::scanf("%u", &n);
  Fibonnacci fib;
  std::printf("%lu\n", fib(n));
}

// eof

C++: #include <cstdint>

using namespace std;

#define MEMO_SIZE 45
int64_t memo[MEMO_SIZE];

void fib_init()
{
  for (uint32_t i = 0; i < MEMO_SIZE; i++) {
    memo[i] = -1;
  }
}

uint32_t fib(uint32_t i)
{
  if (i == 0) {
    return memo[0] = 1;
  } else if (i == 1) {
    return memo[1] = 1;
  } else {
    if (memo[i] != -1)
      return memo[i];
    else {
      return memo[i] = fib(i - 1) + fib(i - 2);
    }
  }
}

#include <iostream>

int32_t main()
{
  fib_init();
  uint32_t i;
  cin >> i;
  cout << fib(i) << endl;
  return 0;
}

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

unordered_map<int,int> memo;
constexpr int fib(int n){
    if(n<2) return 1;
    if (not memo.count(n)) memo[n] = fib(n-1)+fib(n-2);
    return memo[n];

}

int main(void){cin.tie(0);ios::sync_with_stdio(false);
    int n; cin>>n;
    cout<<fib(n);
}

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

int main() {
    int n ;
    cin >> n;
    int a[n+1];
    a[0] = 1;
    a[1] = 1;
    for (int i = 2; i <= n; i++) {
        a[i] = a[i-1] + a[i-2];
    }
    
    cout << a[n] << endl;
    
    return 0;
    
}

C++: #include <bits/stdc++.h>

using namespace std;

#define FOR(i,s,e) for((i)=(s);(i)<(int)(e);(i)++)
#define REP(i,e) FOR(i,0,e)

#define all(o) (o).begin(), (o).end()
#define psb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))

typedef long long ll;
typedef pair<int, int> PII;

const double EPS = 1e-10;

const int M = 2;
int a[M][M], b[M][M], w[M][M];
int n;

//???????£?
//recursive function(with/without memo)

void multiple_mat_ab_b() {
  int i, j, k;
  memset(w, 0, sizeof(w));
  for (i=0; i<M; i++)
    for (j=0; j<M; j++)
      for (k=0; k<M; k++)
        w[i][j] += a[i][k]*b[k][j];

  for (i=0; i<M; i++)
    for (j=0; j<M; j++)
        b[i][j] = w[i][j];
}

void multiple_mat_aa_a() {
  int i, j, k;
  memset(w, 0, sizeof(w));
  for (i=0; i<M; i++)
    for (j=0; j<M; j++)
      for (k=0; k<M; k++)
        w[i][j] += a[i][k]*a[k][j];

  for (i=0; i<M; i++)
    for (j=0; j<M; j++)
        a[i][j] = w[i][j];
}

void pow_mat_a(int k) {
  a[0][0] = a[0][1] = a[1][0] = 1;
  a[1][1] = 0;

  b[0][0] = b[1][1] = 1;
  b[0][1] = b[1][0] = 0;

  while (k) {
    if (k & 1) multiple_mat_ab_b();
    multiple_mat_aa_a();
    k >>= 1;
  }
}

int main() {
  scanf("%d ", &n);
  pow_mat_a(n);
  printf("%d\n", b[1][0]+b[1][1]);

	return 0;
}

C++: #include<iostream>

using namespace std;

int fib(int n);

int memo[45];

int main(){
  int n;

  //??\???
  cin >> n;

  //??????
  cout << fib(n) << endl;

  return 0;
}

int fib(int n){

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