How Fibonacci DP Works

The cache is self.sequence, initialized to [0, 1]. Every call to get(index) checks whether the requested index is already covered and appends only the missing terms. The return value is a list prefix, not a single Fibonacci number: get(10) returns the first ten Fibonacci numbers starting from index 0. Two doctests pin the return shape. Fibonacci().get(10) returns [0, 1, 1, 2, 3, 5, 8, 13, 21, 34], which is ten elements. Fibonacci().get(5) returns [0, 1, 1, 2, 3], which is five elements. Each doctest creates a fresh instance with Fibonacci(), so the cache starts at [0, 1] for both. In the main function below, a single instance is reused across multiple calls, making any repeat lookup O(1).

Python 3.8 introduced the walrus operator (:=) for assignment inside expressions, and this line shows the canonical use: compute a value, assign it to a name, and test it in one expression. The expression index - (len(self.sequence) - 2) computes how many Fibonacci numbers the list is missing to satisfy the request. The subtraction of 2 accounts for the fact that the last valid index in a list of length k is k - 1, and the Fibonacci sequence counts from 0. If difference is less than 1, the sequence already covers the request and the loop body never runs. If it is 1 or more, the loop appends exactly that many terms by summing the last two elements of the list. The final return slices the list to exactly index elements.

The main function creates a single Fibonacci instance on line 34 and enters an interactive loop. This is the key payoff of the class design: the instance persists across every call in the session, so a user who asks for index 100 and then asks again pays the extension cost once and gets the cached result on the second request. A module-level function with a default-argument dict would accomplish the same, but a class makes the cache's lifetime explicit. The loop reads a prompt, accepts exit or quit as sentinels, converts the input to an integer inside a try/except ValueError block per the contribution guide's input-handling requirement, and prints the result. The if __name__ == "__main__" guard on line 50 ensures main() runs only when the file is executed directly.

Appending one element per missing index makes the extension O(n) time. Storing the full sequence makes it O(n) space. For most educational purposes those costs are acceptable, and returning the full prefix list is a natural interface. Reducing space to O(1) requires throwing away all but the last two values, which means a repeat call for any previous index recomputes from scratch. That trade-off matters if memory is tight and repeat calls are rare. The closed-form Binet formula, which uses the golden ratio, gives each term in O(log n) time via fast matrix exponentiation, but introduces floating-point precision issues for large indices. The class-based memoization approach here prioritizes clarity and repeat-call efficiency at the cost of memory proportional to the largest index ever requested. Reading maths/fibonacci.py in this repository shows several of these alternatives side by side.