The original question can be found here.
The question is asking to return the Nth fibonacci number. F(0) = 0, F(1) = 1 and F(n) = F(n - 1) + F(n - 2).
The easist solution is using recursion. If you’re not familiar with this topic, feel free to read this short post here.
class Solution:
def fib(self, n: int) -> int:
if n < 2:
return n
return self.fib(n - 1) + self.fib(n - 2)Time complexity: O(n). Space complexity: O(2^n). Why O(2^n)? Normally for a recursion problem, we can think of each function call as a tree node in a tree. The time complexity will be number of nodes in the tree, which equals to branch factor ^ depth. In this case, branch factor is 2, and depth is n, thus O(2^n).