class Solution {
public:
int fib(int n)
{
int x[] = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986};
return x[n];
}
};

class Solution {
public:
int fib(int n)
{
if(n == 2 || n == 1) return 1;
if(n <= 0) return 0;
return fib(n - 2) + fib(n - 1);
}
};


class Solution {
private:
map<int,int> cache;
public:
int fib(int n)
{
if(n == 2 || n == 1) return 1;
if(n <= 0) return 0;

int p,q;

auto pitr = cache.find(n - 1);
if(pitr != cache.end()){
p = pitr->second;
}else{
p = fib(n - 1);
cache[n - 1] = p;
}

auto qitr = cache.find(n - 2);
if(qitr != cache.end()){
q = qitr->second;
}else{
q = fib(n - 2);
cache[n - 2] = q;
}

return p+q;
}
};


class Solution {
private:
map<int,int> cache;
public:
int fib(int n)
{
if(n == 2 || n == 1) return 1;
if(n <= 0) return 0;

int p,q;
int m = 2;
auto pitr = cache.find((n - 1) % m);
if(pitr != cache.end()){
p = pitr->second;
}else{
p = fib((n - 1) );
cache[(n - 1) % m] = p;
}

auto qitr = cache.find((n - 2) % m);
if(qitr != cache.end()){
q = qitr->second;
}else{
q = fib((n - 2) );
cache[(n - 2) % m] = q;
}

return p+q;
}
};


$$f(n+2) = f(n+1) + f(n)$$

$$f(n) = k_1 ({\dfrac{1 + \sqrt[]{5}}{2}})^n + k_2 ({\dfrac{1 - \sqrt[]{5}}{2}})^n$$

syms k1 k2 A
five = sym( 5, 'f' )
A = [
( (1+sqrt(five))/2 ), ( (1-sqrt(five))/2 );
( (1+sqrt(five))/2 )^2, ( (1-sqrt(five))/2 )^2
]
b = [1;1]
x = A \ b

A = (sym 2×2 matrix)

⎡ 1   √5     1   √5  ⎤
⎢ ─ + ──     ─ - ──  ⎥
⎢ 2   2      2   2   ⎥
⎢                    ⎥
⎢        2          2⎥
⎢⎛1   √5⎞   ⎛1   √5⎞ ⎥
⎢⎜─ + ──⎟   ⎜─ - ──⎟ ⎥
⎣⎝2   2 ⎠   ⎝2   2 ⎠ ⎦

b =

1
1

x = (sym 2×1 matrix)

⎡ √5 ⎤
⎢ ── ⎥
⎢ 5  ⎥
⎢    ⎥
⎢-√5 ⎥
⎢────⎥
⎣ 5  ⎦


$$f(n) = \dfrac{1}{\sqrt[]{5}} ({\dfrac{1 + \sqrt[]{5}}{2}})^n - \dfrac{1}{\sqrt[]{5}} ({\dfrac{1 - \sqrt[]{5}}{2}})^n$$

class Solution {
public:
int fib(int n)
{
if(n <= 1) return n;
double r =  (1.0 / sqrt(5.0)) * (
pow(( (1.0 + sqrt(5.0)) / 2.0 ), n) +
pow(( (1.0 - sqrt(5.0)) / 2.0 ), n)
);
return round(r);
}
};