Fibonacci Sequence (Dynamic Programming)

How Fibonacci with Dynamic Programming Works

The Fibonacci sequence is defined as follows: the first two numbers are 0 and 1, and each subsequent number is the sum of the two preceding ones. Dynamic programming optimizes this calculation by storing previously computed values, allowing us to calculate the nth Fibonacci number in O(n) time complexity.

The algorithm:

1. Initialize an array with the first two Fibonacci numbers: [0, 1]
2. For each subsequent position i, calculate F[i] = F[i-1] + F[i-2]
3. Continue until we've calculated the nth number

This approach is much more efficient than the recursive method, especially for larger values of n.

function fibonacciDP(n):
    if n <= 1:
        return n
    
    dp = array of size n+1
    dp[0] = 0
    dp[1] = 1
    
    for i from 2 to n:
        dp[i] = dp[i-1] + dp[i-2]
        visualize(dp, i)
    
    return dp[n]

function visualize(dp, currentIndex):
    // Update UI to show:
    // 1. The current state of the dp array
    // 2. Highlight the current index being calculated
    // 3. Show the calculation dp[i] = dp[i-1] + dp[i-2]