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 <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 <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9+7,MAX = 1e5;

int hibo[50];

int fibo(int i)
{	
	if(i==0||i==1)return hibo[i] = 1;
	if(hibo[i]!=0)return hibo[i];
	return hibo[i] = fibo(i-1)+fibo(i-2);
}

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

C++: #include <iostream>
using namespace std;
 
int main() {
	int fib[45]={1,1},i;
for(i=1;i<=44;i++){
fib[i]=fib[i-1]+fib[i-2];
}
	return 0;
}

C++: #include<bits/stdc++.h>
using namespace std;
using ll=long long;
using vec=vector<ll>;
using mat=vector<vec>;
#define For(i,a,b) for(i=a;i<b;i++)
#define rep(i,N) For(i,0,N)
#define rep1(i,N) For(i,1,N)
#define all(v) (v).begin(),(v).end()
#define allr(v) (v).rbegin(),(v).rend()
#define vsort(v) sort(all(v))
#define vrsort(v) sort(allr(v))
#define mod 1000000007
using datas=pair<ll,ll>;
using tdata=pair<datas,ll>;

long mmid(long a,long b,long c){return a<b?(b<c?b:max(a,c)):(b>c?b:min(a,c));}

ll modinv(ll a) {
  ll b=mod,u=1,v=0,t;
  while(b){
    t=a/b;
    a-=t*b; swap(a,b);
    u-=t*v; swap(u,v);
  }
  return (u+mod)%mod;
}

ll moddevide(ll a,ll b){return (a*modinv(b))%mod;}

ll modncr(ll n,ll r){
  ll i,plus=1;
  rep(i,r){
    plus=(plus*(n-i))%mod;
    plus=moddevide(plus,i+1);
  }
  return plus;
}

ll modncrlistp[200000],modncrlistm[200000];

ll modncrs(ll n,ll r){
  ll i,j;
  if(modncrlistp[n]==0){
    for(i=n;i>=0;i--){
      if(modncrlistp[i])break;
    }
    if(i<0){
      modncrlistp[0]=1;
      rep1(i,n+1){
        modncrlistp[i]=(modncrlistp[i-1]*i)%mod;
      }
    }else{
      For(j,i+1,n+1){
        modncrlistp[j]=(modncrlistp[j-1]*j)%mod;
      }
    }
  }
  if(modncrlistm[n]==0){
    for(i=n;i>=0;i--){
      if(modncrlistm[i])break;
    }
    if(i<0){
      modncrlistm[0]=1;
      rep1(i,n+1){
        modncrlistm[i]=(modncrlistm[i-1]*modinv(i))%mod;
      }
    }else{
      For(j,i+1,n+1)modncrlistm[j]=(modncrlistm[j-1]*modinv(j))%mod;
    }
  }
  return (((modncrlistp[n]*modncrlistm[r])%mod)*modncrlistm[n-r])%mod;
}

ll euclidean_gcd(ll a, ll b) {
  if(a<b) return euclidean_gcd(b, a);
  ll r;
  while ((r=a%b)){a=b;b=r;}
  return b;
}

ll countdigits(ll n){
  ll ans=0;
  while(n){n/=10;ans++;}
  return ans;
}

ll sumdigits(ll n){
  ll ans=0;
  while(n){ans+=n%10;n/=10;}
  return ans;
}

void printmap(vector<ll>& a,ll H,ll W){
  ll i,j;
  For(i,0,H+2){
    For(j,0,W+2){cout<<a[i*(W+2)+j];}
    cout<<endl;
  }
}
void inputmap(vector<ll>& a,ll H,ll W){
  ll i,j;
  string ss;
  For(i,1,H+1){
    cin>>ss;
    For(j,1,W+1){
      if(ss[j-1]=='#'){
        a[i*(W+2)+j]=1;
      }else{
        a[i*(W+2)+j]=0;
      }
    }
  }
}
ll lpow(ll a,ll b){
  ll i,res=1;
  rep(i,b){
    res*=a;
  }
  return res;
}

struct unionfind{
  vector<ll> par,treesize;
  unionfind(ll N){
    par.resize(N);
    for(ll i=0;i<N;i++)par[i]=i;
    treesize.resize(N);
    for(ll i=0;i<N;i++)treesize[i]=1;
  }
  ll root(ll x){
    ll r;
    if(par[x]==x)return x;
    r=root(par[x]);
    if(par[x]!=r){
      treesize[r]+=treesize[x];
      treesize[x]=0;
      par[x]=r;
    }
    return r;
  }
  void unite(ll x,ll y){
    ll px=root(x);
    ll py=root(y);
    if(px!=py){
      par[px]=py;
      treesize[py]+=treesize[px];
      treesize[px]=0;
    }
  }
  bool parcheck(ll x,ll y){
    ll px=root(x);
    ll py=root(y);
    return px==py;
  }
  ll size(ll x){
    ll px=root(x);
    return treesize[px];
  }
};

int main(){
  ll i,j=0,N,M,cnt=0;
  cin>>N;
  vec v(N+1,1);
  if(N<2){cout<<1<<endl;return 0;}
  For(i,2,N+1){
    v[i]=v[i-1]+v[i-2];
  }
  cout<<v[N]<<endl;
}

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

int fib(int n, int a, int b);

int main()
{
	int n;
	cin >> n;
	cout << fib(n - 1, 1, 1) << endl;
	return (0);
}


int fib(int n, int a, int b){
	int f;
	f = a;
	if (n >= 1){
		return(fib(n - 1, a + b, a));
  }
	else {
	  return (f);
	}
}

C++: #include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector<int> fibonacci;
int main(void){
    int n;
    cin >> n;
    int b = 1;
    int c = 1;
    fibonacci.push_back(b);
    fibonacci.push_back(c);
    for(int i=2;i<n;i++){
        int a = b + c;
        fibonacci.push_back(a);
        c = b;
        b = a;
    }
    cout << fibonacci[n-1] + fibonacci[n-2] << endl;
    return 0;
}

C++: #include <iostream>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cmath>
#define rep(i,a,b) for(int (i)=(a);i<(b);i++)
#define INF 100000000
#define MAX_N 1000000
using namespace std;

int main(){
    int n;
    int fib[50];
    cin>>n;
    fib[0]=1;
    fib[1]=1;
    rep(i,2,n+1){
        fib[i]=fib[i-1]+fib[i-2];
    }
    cout<<fib[n]<<endl;
    return 0;
}

C++: #include<bits/stdc++.h>
#define rep(i,n) for(int i = 0;i<n;i++)
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0;}
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0;}

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

C++: /* 以下は動的計画法を用いずにナイーブに書いたプログラム
#include<iostream>
using namespace std;

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

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

    return 0;
}
*/

#include<iostream>
using namespace std;

int fib[45] = {0};

void solve(int n) {
    if (n == 0 || n == 1) {
        fib[n] = 1;
        return;
    }
    if (fib[n - 2] == 0) solve(n - 2);
    if (fib[n - 1] == 0) solve(n - 1);
    fib[n] = fib[n - 1] + fib[n - 2];
    return;
}

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

C++: #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
const double PI = acos(-1);
const ll MOD = 1000000007;
using Graph = vector<vector<int>>;

int main() {
  int n; cin >> n;
  vector<ll> a(n+1);

  a[0] = a[1] = 1;

  for (int i = 2; i <= n; i++) a[i] = a[i-1] + a[i-2];

  cout << a[n] << endl;
}

C++: #include <stdio.h>
#define rep(i, n) for(int i = 0; i < n; ++i)
int f[50];

void fi(int a) {
  f[a] = f[a - 2] + f[a - 1];
}

int main(void) {
  int n;
  scanf("%d", &n);
  rep(i, 50) f[i] = 0;
  f[0] = 1, f[1] = 1;
  for(int i = 2; i < 50; ++i) fi(i);
  printf("%d\n", f[n]);
  return 0;
}

C++: #include <cstdio>
#include <iostream>

using namespace std;

int fib(int n) {

	if (n == 0 || n == 1)
		return 1;

	return fib(n - 1) + fib(n - 2);
}

int main() {

	int n;
	scanf("%d", &n);

	cout << fib(n) << endl;

	return 0;

}