Memoised Fibonacci

Lab Java Intermediate 20 points

Compute F(n) (F0 = 0, F1 = 1) with recursion plus a long[] memo array.

Input

One integer 0–90.

Output

F(n)

Example

Input

Output

Sample input available Sample output available

Editor

Java

Hints

Store each answer the first time you compute it.

Solution explanation

Without the memo, fib(90) would take longer than the age of the universe.

Show solution

import java.util.Scanner;

public class Main {
    static long[] memo = new long[91];

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

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println(fib(sc.nextInt()));
    }
}

Output

Answer