## Finding the nth Fibonacci Number Using Dynamic Programming in Python
The Fibonacci sequence is a well-known series in mathematics, where each number in the sequence is the sum of the two preceding ones. The sequence typically starts with 0 and 1. The objective is often to find the nth Fibonacci number efficiently, particularly for larger values of n.
Dynamic programming provides an optimal solution by storing previously computed values to avoid redundant calculations. This approach significantly improves performance compared to a naive recursive solution.
Dynamic Programming Approach
The dynamic programming method can be implemented using either a bottom-up approach or a top-down approach with memoization. Here, the bottom-up approach is demonstrated, where an array is used to store computed Fibonacci numbers.
Python Function Implementation
def fibonacci(n):
if n < 0:
raise ValueError("Input cannot be negative")
elif n == 0:
return 0
elif n == 1:
return 1
# Create an array to store Fibonacci numbers up to n
fib = [0] * (n + 1)
fib[0] = 0
fib[1] = 1
# Build the Fibonacci sequence iteratively
for i in range(2, n + 1):
fib[i] = fib[i - 1] + fib[i - 2]
return fib[n]
# Example usage:
nth_fibonacci = fibonacci(10)
print(f"The 10th Fibonacci number is: {nth_fibonacci}")
Explanation of the Code
1. Input Validation: The function first checks if the input n is negative, raising a ValueError in such cases. It then directly returns the correct Fibonacci number for inputs 0 and 1.
2. Array Initialization: An array fib is created with a size of n + 1 to store Fibonacci values. The first two values are defined as fib[0] = 0 and fib[1] = 1.
3. Iterative Calculation: A for loop iterates from 2 to n, calculating each Fibonacci number by summing the two preceding numbers stored in the array.
4. Return Result: Finally, the function returns fib[n], which is the nth Fibonacci number.
Performance
This dynamic programming solution runs in O(n) time complexity and uses O(n) space due to the storage of Fibonacci numbers in an array, making it efficient and suitable for larger values of n.
By employing this method, the nth Fibonacci number can be calculated swiftly and effectively, showcasing the strength of dynamic programming in solving recursive problems.