Fibonacci Sequence and Dynamic Programming
Welcome to Day 31 of our 60 Days of Coding Algorithm Challenge! Today, we’ll dive deeper into Dynamic Programming by exploring the Fibonacci sequence, a classic problem that demonstrates the power of DP.
The Fibonacci Sequence
The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones. It typically starts with 0 and 1, and the sequence goes as follows:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …
Mathematically, it can be defined as:
F(n) = F(n-1) + F(n-2), where F(0) = 0 and F(1) = 1
Naive Recursive Approach
Let’s start with a naive recursive implementation:
1def fibonacci_naive(n):
2 if n <= 1:
3 return n
4 return fibonacci_naive(n-1) + fibonacci_naive(n-2)
5
6# Example usage
7print(fibonacci_naive(10)) # Output: 55
While this implementation is simple and intuitive, it has a time complexity of O(2^n), making it extremely inefficient for large values of n.
Dynamic Programming Approaches
We can significantly improve the efficiency using Dynamic Programming. Let’s explore both top-down (memoization) and bottom-up (tabulation) …
Fibonacci Sequence and Dynamic Programming
Welcome to Day 31 of our 60 Days of Coding Algorithm Challenge! Today, we’ll dive deeper into Dynamic Programming by exploring the Fibonacci sequence, a classic problem that demonstrates the power of DP.
The Fibonacci Sequence
The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones. It typically starts with 0 and 1, and the sequence goes as follows:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …
Mathematically, it can be defined as:
F(n) = F(n-1) + F(n-2), where F(0) = 0 and F(1) = 1
Naive Recursive Approach
Let’s start with a naive recursive implementation:
1def fibonacci_naive(n):
2 if n <= 1:
3 return n
4 return fibonacci_naive(n-1) + fibonacci_naive(n-2)
5
6# Example usage
7print(fibonacci_naive(10)) # Output: 55
While this implementation is simple and intuitive, it has a time complexity of O(2^n), making it extremely inefficient for large values of n.
Dynamic Programming Approaches
We can significantly improve the efficiency using Dynamic Programming. Let’s explore both top-down (memoization) and bottom-up (tabulation) approaches.
Top-Down Approach (Memoization)
1def fibonacci_memo(n, memo={}):
2 if n in memo:
3 return memo[n]
4 if n <= 1:
5 return n
6 memo[n] = fibonacci_memo(n-1, memo) + fibonacci_memo(n-2, memo)
7 return memo[n]
8
9# Example usage
10print(fibonacci_memo(100)) # Fast, even for large n
Time Complexity: O(n)
Space Complexity: O(n)
Bottom-Up Approach (Tabulation)
1def fibonacci_tab(n):
2 if n <= 1:
3 return n
4 dp = [0] * (n + 1)
5 dp[1] = 1
6 for i in range(2, n + 1):
7 dp[i] = dp[i-1] + dp[i-2]
8 return dp[n]
9
10# Example usage
11print(fibonacci_tab(100)) # Also fast for large n
Time Complexity: O(n)
Space Complexity: O(n)
Space-Optimized Bottom-Up Approach
We can further optimize the space complexity:
1def fibonacci_optimized(n):
2 if n <= 1:
3 return n
4 a, b = 0, 1
5 for _ in range(2, n + 1):
6 a, b = b, a + b
7 return b
8
9# Example usage
10print(fibonacci_optimized(100)) # Efficient in both time and space
Time Complexity: O(n)
Space Complexity: O(1)
Comparison of Approaches
Let’s compare the performance of these approaches:
1import time
2
3def time_function(func, n):
4 start = time.time()
5 result = func(n)
6 end = time.time()
7 return result, end - start
8
9n = 30
10print(f"Calculating F({n}):")
11
12result, time_naive = time_function(fibonacci_naive, n)
13print(f"Naive Recursive: {result} (Time: {time_naive:.6f} seconds)")
14
15result, time_memo = time_function(fibonacci_memo, n)
16print(f"Memoization: {result} (Time: {time_memo:.6f} seconds)")
17
18result, time_tab = time_function(fibonacci_tab, n)
19print(f"Tabulation: {result} (Time: {time_tab:.6f} seconds)")
20
21result, time_opt = time_function(fibonacci_optimized, n)
22print(f"Optimized: {result} (Time: {time_opt:.6f} seconds)")
Advanced: Matrix Exponentiation
For very large n, we can use matrix exponentiation to calculate Fibonacci numbers in O(log n) time:
1def fibonacci_matrix(n):
2 def matrix_multiply(a, b):
3 return [
4 [a[0][0]*b[0][0] + a[0][1]*b[1][0], a[0][0]*b[0][1] + a[0][1]*b[1][1]],
5 [a[1][0]*b[0][0] + a[1][1]*b[1][0], a[1][0]*b[0][1] + a[1][1]*b[1][1]]
6 ]
7
8 def matrix_power(matrix, power):
9 if power == 1:
10 return matrix
11 if power % 2 == 0:
12 half_power = matrix_power(matrix, power // 2)
13 return matrix_multiply(half_power, half_power)
14 return matrix_multiply(matrix, matrix_power(matrix, power - 1))
15
16 if n <= 1:
17 return n
18 base_matrix = [[1, 1], [1, 0]]
19 result_matrix = matrix_power(base_matrix, n - 1)
20 return result_matrix[0][0]
21
22# Example usage
23print(fibonacci_matrix(1000)) # Can calculate very large Fibonacci numbers
Time Complexity: O(log n)
Space Complexity: O(log n) due to the recursive calls in matrix_power
Exercise
Implement a function to find the nth Fibonacci number modulo a given number M. This is useful for handling very large Fibonacci numbers.
The Fibonacci sequence can be extended to negative indices. Implement a function that can calculate F(n) for any integer n, positive or negative.
Implement a generator function that yields Fibonacci numbers indefinitely. Use this to find the first Fibonacci number greater than a million.
Summary
Today, we explored the Fibonacci sequence as a classic example of Dynamic Programming. We implemented and compared various approaches, from naive recursion to optimized DP solutions and even matrix exponentiation for very large numbers.
Understanding these different approaches to the Fibonacci sequence provides insights into the power of Dynamic Programming and the trade-offs between time and space complexity.
Tomorrow, we’ll explore another classic Dynamic Programming problem: the Longest Common Subsequence. Stay tuned!