#include <iostream>
#include <unordered_map>
using namespace std;

long fib(long n, unordered_map<long,long> &memo){
    long res;
   
    if (n == 0 || n == 1){
        return 1;
    }
    if (memo.find(n) == memo.end()){
        res = fib(n-1,memo) + fib(n-2,memo);
        memo[n] = res;
    } else {
        res = memo[n];
    }
    return res;
}

long fib_bu(long n){
    long f0, f1;
    f0 = f1 = 1;
    for (long i = 2; i <= n; i++){
        long t = f0+f1;
        f0 = f1;
        f1 = t;
    }
    return f1;
}


int main()
{
    unordered_map<long,long> memo;
   
    cout << fib(100,memo) << endl;
    cout << fib_bu(100) << endl;

    return 0;
}

/*

main =>
%    println(fib(1000)),
%    println(bc(10,3)).
%     println(count_paths(50,50)).
%    lcs("AACCGTACT","GTACTTACC", Res, Len),
%    println(res=Res),
%    println(len=Len).
     opt(8,Ts,Pt),
     printf("jobs = %w profits = %w\n",Ts,Pt).
   
table
fib(0) = 1.
fib(1) = 1.
fib(N) = fib(N-1) + fib(N-2).

% Binomial Coefficient

table
bc(_,0) = 1.
bc(N,N) = 1.
bc(N,K) = bc(N-1,K-1) + bc(N-1,K).

% Count paths on an N*N grid from the left-upper corner to the right-bottom corner
table
count_paths(1,_) = 1.
count_paths(_,1) = 1.
count_paths(R,C) = count_paths(R-1,C) + count_paths(R,C-1).

% longest common subsequence
table (+,+,-,max)
lcs([],_,Res,Len) => Res = [], Len = 0.
lcs(_,[],Res,Len) => Res = [], Len = 0.
lcs([X|S1],[X|S2],Res,Len) ?=>
  lcs(S1,S2,Res1,Len1),
  Res = [X|Res1],
  Len = Len1+1.
lcs([_|S1],S2,Res,Len) ?=>
  lcs(S1,S2,Res,Len).
lcs(S1,[_|S2],Res,Len) =>
  lcs(S1,S2,Res,Len).

% weighted interval scheduling
p(1) = 0.
p(2) = 0.
p(3) = 0.
p(4) = 1.
p(5) = 0.
p(6) = 2.
p(7) = 3.
p(8) = 5.

index (+,-,-)
job(1,1,4).
job(2,3,5).
job(3,0,6).
job(4,4,7).
job(5,3,8).
job(6,5,9).
job(7,6,10).
job(8,8,11).

table (+,-,max)
opt(0,Ts,Pt) => Ts = [], Pt = 0.
opt(J,Ts,Pt) ?=>
    Ts = [J|Ts1],
    opt(p(J),Ts1,Pt1),
    job(J,Start,End),
    Pt = Pt1+(End-Start).
opt(J,Ts,Pt) =>
   opt(J-1,Ts,Pt).
*/