Compute Fibonacci with memoization

Summary

Implement the Fibonacci sequence using recursion and memoization to avoid exponential time.

Problem statement

The Fibonacci sequence is defined as: F(0) = 0, F(1) = 1, and for n > 1, F(n) = F(n-1) + F(n-2). A naive recursive implementation computes the same subproblems repeatedly and takes exponential time. In this lesson you will implement fib(n) using memoization (caching of computed results) to reduce the time complexity to O(n). Requirements: - Implement fib(n) that accepts a non-negative integer n and returns the nth Fibonacci number. - Use recursion combined with memoization (a cache/dictionary) to store intermediate results. - For invalid input (negative integers), raise a ValueError.

Task

Write a function fib(n) that returns the nth Fibonacci number (0-indexed) using memoization to achieve linear time.

Examples

Input format

A single non-negative integer n passed as an argument to fib(n).

Output format

An integer equal to the nth Fibonacci number (0-indexed).

Constraints

0 <= n <= 1000. Use memoization to keep runtime roughly O(n). Be careful with recursion depth for very large n (n > 1000 may hit recursion limits).

Samples