Leetcode 0509. Fibonacci Number

Problem statement

https://leetcode.com/problems/fibonacci-number/

This is very very classical problem and I think already everything was said about different solutions. Here is another straightforward solution, where we use lru_cache function and recursion.

Complexity

Time complexity is just O(n), space complexity is O(n) as well, because we use lru_cache.

Remark

Note, that there is also O(log n) time complexity solution as well if you need it for big n and evaluate given some modulo. However here n is very small and it is not worth it.

Code

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