//Fibonacci number using memoization.
#include<bits/stdc++.h>
using namespace std;
 
int fibRec(int n, vector<int> &mem) {
 
    // Base case
    if (n <= 1) {
        return n;
    }
 
    // To check if output already exists
    if (mem[n] != -1) {
        return mem[n];
    }
 
    // Calculate and save output for future use
    mem[n] = fibRec(n - 1, mem) + fibRec(n - 2, mem);
 
    return mem[n];
}
 
int fib(int n) {
    vector<int> mem(n + 1, -1);
    return fibRec(n, mem);
}
 
int main() {
    int n = 10;
    cout << fib(n);
    return 0;
}

Ly9GaWJvbmFjY2kgbnVtYmVyIHVzaW5nIG1lbW9pemF0aW9uLgojaW5jbHVkZTxiaXRzL3N0ZGMrKy5oPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKaW50IGZpYlJlYyhpbnQgbiwgdmVjdG9yPGludD4gJm1lbSkgewogIAogICAgLy8gQmFzZSBjYXNlCiAgICBpZiAobiA8PSAxKSB7CiAgICAgICAgcmV0dXJuIG47CiAgICB9CgogICAgLy8gVG8gY2hlY2sgaWYgb3V0cHV0IGFscmVhZHkgZXhpc3RzCiAgICBpZiAobWVtW25dICE9IC0xKSB7CiAgICAgICAgcmV0dXJuIG1lbVtuXTsKICAgIH0KCiAgICAvLyBDYWxjdWxhdGUgYW5kIHNhdmUgb3V0cHV0IGZvciBmdXR1cmUgdXNlCiAgICBtZW1bbl0gPSBmaWJSZWMobiAtIDEsIG1lbSkgKyBmaWJSZWMobiAtIDIsIG1lbSk7CgogICAgcmV0dXJuIG1lbVtuXTsKfQoKaW50IGZpYihpbnQgbikgewogICAgdmVjdG9yPGludD4gbWVtKG4gKyAxLCAtMSk7CiAgICByZXR1cm4gZmliUmVjKG4sIG1lbSk7Cn0KCmludCBtYWluKCkgewogICAgaW50IG4gPSAxMDsKICAgIGNvdXQgPDwgZmliKG4pOwogICAgcmV0dXJuIDA7Cn0=