Day 31

Day 31: Fibonacci Sequence and Dynamic Programming

31/60 Days

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 #

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!

Fibonacci Sequence and Dynamic Programming #

The Fibonacci Sequence #

Naive Recursive Approach #

Dynamic Programming Approaches #

Fibonacci Sequence and Dynamic Programming #

The Fibonacci Sequence #

Naive Recursive Approach #

Dynamic Programming Approaches #

Top-Down Approach (Memoization) #

Bottom-Up Approach (Tabulation) #

Space-Optimized Bottom-Up Approach #

Comparison of Approaches #

Advanced: Matrix Exponentiation #

Exercise #

Summary #

Continue Reading

Re-enter Password

Confirm Action