# Function for nth fibonacci # number - Dynamic Programming # Taking 1st two fibonacci numbers as 0 and 1 FibArray = [0, 1] def fibonacci(n): # Check is n is less # than 0 if n < 0: print("Incorrect input") # Check is n is less # than len(FibArray) elif n < len(FibArray): return FibArray[n] else: FibArray.append(fibonacci(n - 1) + fibonacci(n - 2)) return FibArray[n] # Driver Program print(fibonacci(9)) # This code is contributed by Saket Modi