Memoised Fibonacci

Lab C++ Intermediate 20 points

Compute F(n) for n ≤ 90 with recursion and a vector<long long> memo initialised to -1.

Input

One integer.

Output

F(n)

Example

Input

Output

Sample input available Sample output available

Editor

C++

Hints

Store each answer the first time it's computed.

Solution explanation

Memoisation turns exponential recursion into linear time.

Show solution

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

vector<long long> memo(91, -1);

long long fib(int n) {
    if (n < 2) return n;
    if (memo[n] != -1) return memo[n];
    return memo[n] = fib(n - 1) + fib(n - 2);
}

int main() {
    int n;
    cin >> n;
    cout << fib(n) << "\n";
    return 0;
}

Output

Answer