# Title: Fibonacci with memoization
# Heading: Python Program for Fibonacci Using Memoization
# Level: intermediate
# Tags: fibonacci, memoization, dp, recursion, cache
# Time: O(n)
# Space: O(n)
# About: Works out Fibonacci numbers with recursion, remembering each answer in a dict so that no number is ever calculated twice.

memo = {0: 0, 1: 1}  # the answers known so far


def fib(n):
    """The nth Fibonacci number, each one worked out only once."""
    if n not in memo:
        memo[n] = fib(n - 1) + fib(n - 2)
    return memo[n]


print("Fibonacci 10:", fib(10))
print("Fibonacci 50:", fib(50))