Given n, return F(n) where F(0) = 0, F(1) = 1, and F(n) = F(n-1) + F(n-2) for n > 1. Use two variables to track the previous two values and iterate n times, updating them each step.
Use recursion mirroring the mathematical definition, but cache results to avoid redundant calculations. Python's @lru_cache decorator handles memoization automatically.
""" 0509.1 - Solution 1 - Iterative (Bottom-Up) """
#####################################################################################
# Classes
#####################################################################################
class Solution:
"""Solution Class"""
def fib(self, n: int) -> int:
"""Fibonacci Number Function"""
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
#####################################################################################
# Functions
#####################################################################################
def testcase():
"""Test Function"""
print(Solution().fib(0)) # Expected: 0
print(Solution().fib(1)) # Expected: 1
print(Solution().fib(2)) # Expected: 1
print(Solution().fib(3)) # Expected: 2
print(Solution().fib(4)) # Expected: 3
print(Solution().fib(10)) # Expected: 55
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()
""" 0509.2 - Solution 2 - Recursive with Memoization """
#####################################################################################
# Imports
#####################################################################################
from functools import lru_cache
#####################################################################################
# Classes
#####################################################################################
class Solution:
"""Solution Class"""
@lru_cache(maxsize=None)
def fib(self, n: int) -> int:
"""Fibonacci Number Function"""
if n < 2:
return n
return self.fib(n - 1) + self.fib(n - 2)
#####################################################################################
# Functions
#####################################################################################
def testcase():
"""Test Function"""
print(Solution().fib(0)) # Expected: 0
print(Solution().fib(1)) # Expected: 1
print(Solution().fib(2)) # Expected: 1
print(Solution().fib(3)) # Expected: 2
print(Solution().fib(4)) # Expected: 3
print(Solution().fib(10)) # Expected: 55
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()