Fibonacci Dynamic Programming: Interactive Algorithm Visualization

Description

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, usually starting with 0 and 1. Dynamic programming optimizes the calculation by storing previously computed values.

F(n) = F(n-1) + F(n-2)

where F(0) = 0 and F(1) = 1

How It Works

Initialize variables for the two previous numbers (0 and 1)
For each step up to n:
- Calculate next number by adding previous two
- Update previous numbers
Return the final calculated number

Visualization

Enter a number to calculate its Fibonacci value

Complexity Analysis

Time Complexity

O(n) where:

n is the input number
Each number is calculated exactly once
No recursive calls or redundant calculations

Space Complexity

O(1) because:

Only three variables are used regardless of input size
No additional data structures needed

Advantages and Disadvantages

Advantages

Linear time complexity
Constant space complexity
Simple implementation
No recursion overhead
Handles large inputs efficiently

Disadvantages

Limited by integer overflow for large n
Not suitable for calculating specific terms without computing previous ones
May need BigInteger for large numbers
Cannot easily compute arbitrary terms in sequence

Implementation


class Fibonacci:
    @staticmethod
    def fibonacci_dp(n: int) -> int:
        """
        Calculate the nth Fibonacci number using dynamic programming.
        
        Args:
            n: The position in the Fibonacci sequence (0-based)
            
        Returns:
            The nth Fibonacci number
            
        Raises:
            ValueError: If n is negative
        """
        if n < 0:
            raise ValueError("Fibonacci sequence is not defined for negative numbers")
        
        if n <= 1:
            return n
            
        prev, curr = 0, 1
        
        for _ in range(2, n + 1):
            prev, curr = curr, prev + curr
            
        return curr
    
    @staticmethod
    def fibonacci_sequence(n: int) -> list[int]:
        """
        Generate Fibonacci sequence up to the nth number.
        
        Args:
            n: The position in the Fibonacci sequence (0-based)
            
        Returns:
            List containing the Fibonacci sequence up to n
        """
        if n < 0:
            raise ValueError("Fibonacci sequence is not defined for negative numbers")
            
        sequence = [0]
        if n == 0:
            return sequence
            
        sequence.append(1)
        
        for i in range(2, n + 1):
            sequence.append(sequence[i-1] + sequence[i-2])
            
        return sequence

# Example usage
if __name__ == "__main__":
    # Calculate single Fibonacci number
    n = 10
    result = Fibonacci.fibonacci_dp(n)
    print(f"F({n}) = {result}")
    
    # Generate sequence
    sequence = Fibonacci.fibonacci_sequence(n)
    print(f"Fibonacci sequence up to {n}:")
    print(" ".join(map(str, sequence)))


#include <iostream>
#include <vector>
#include <stdexcept>

class Fibonacci {
public:
    static long long fibonacciDP(int n) {
        if (n < 0) {
            throw std::invalid_argument("Fibonacci sequence is not defined for negative numbers");
        }
        
        if (n <= 1) {
            return n;
        }
        
        long long prev = 0, curr = 1;
        
        for (int i = 2; i <= n; ++i) {
            long long next = prev + curr;
            prev = curr;
            curr = next;
        }
        
        return curr;
    }
    
    static std::vector<long long> fibonacciSequence(int n) {
        if (n < 0) {
            throw std::invalid_argument("Fibonacci sequence is not defined for negative numbers");
        }
        
        std::vector<long long> sequence;
        sequence.push_back(0);
        
        if (n == 0) {
            return sequence;
        }
        
        sequence.push_back(1);
        
        for (int i = 2; i <= n; ++i) {
            sequence.push_back(sequence[i-1] + sequence[i-2]);
        }
        
        return sequence;
    }
    
    static void printSequence(const std::vector<long long>& sequence) {
        for (size_t i = 0; i < sequence.size(); ++i) {
            std::cout << sequence[i];
            if (i < sequence.size() - 1) {
                std::cout << " ";
            }
        }
        std::cout << std::endl;
    }
};

// Example usage
int main() {
    try {
        int n = 10;
        
        // Calculate single Fibonacci number
        long long result = Fibonacci::fibonacciDP(n);
        std::cout << "F(" << n << ") = " << result << std::endl;
        
        // Generate sequence
        std::cout << "Fibonacci sequence up to " << n << ":" << std::endl;
        auto sequence = Fibonacci::fibonacciSequence(n);
        Fibonacci::printSequence(sequence);
        
    } catch (const std::exception& e) {
        std::cerr << "Error: " << e.what() << std::endl;
        return 1;
    }
    
    return 0;
}


using System;
using System.Collections.Generic;

public class Fibonacci
{
    public static long FibonacciDP(int n)
    {
        if (n < 0)
        {
            throw new ArgumentException("Fibonacci sequence is not defined for negative numbers");
        }
        
        if (n <= 1)
        {
            return n;
        }
        
        long prev = 0, curr = 1;
        
        for (int i = 2; i <= n; i++)
        {
            long next = prev + curr;
            prev = curr;
            curr = next;
        }
        
        return curr;
    }
    
    public static List<long> FibonacciSequence(int n)
    {
        if (n < 0)
        {
            throw new ArgumentException("Fibonacci sequence is not defined for negative numbers");
        }
        
        var sequence = new List<long> { 0 };
        
        if (n == 0)
        {
            return sequence;
        }
        
        sequence.Add(1);
        
        for (int i = 2; i <= n; i++)
        {
            sequence.Add(sequence[i-1] + sequence[i-2]);
        }
        
        return sequence;
    }
    
    public static void PrintSequence(List<long> sequence)
    {
        Console.WriteLine(string.Join(" ", sequence));
    }
    
    // Example usage
    public static void Main()
    {
        try
        {
            int n = 10;
            
            // Calculate single Fibonacci number
            long result = FibonacciDP(n);
            Console.WriteLine($"F({n}) = {result}");
            
            // Generate sequence
            Console.WriteLine($"Fibonacci sequence up to {n}:");
            var sequence = FibonacciSequence(n);
            PrintSequence(sequence);
        }
        catch (Exception e)
        {
            Console.WriteLine($"Error: {e.Message}");
        }
    }
}

Quick Info

Fibonacci (Dynamic Programming)