BinarySearch 0056 Nth Fibonacci Number

Problem statement

https://binarysearch.com/problems/Nth-Fibonacci-Number/

Solution

Equal to leetcode 0509. Fibonacci Number

Complexity

It is O(n) for time and space.

Code

class Solution:
    @lru_cache(None)
    def solve(self, N):
        return N if N <= 1 else self.solve(N-1) + self.solve(N-2)