Program Overview

This program calculates the Fibonacci sequence using dynamic programming to optimize the computation of Fibonacci numbers. Instead of using a simple recursive approach, which can be inefficient due to repeated calculations, dynamic programming stores previously computed results in an array to avoid redundant work.

Program Structure

• Input: An integer n representing the position in the Fibonacci sequence.
• Dynamic Programming Array: An array to store Fibonacci numbers computed from 0 to n.
• Output: The Fibonacci number at the given position n.

C Program

#include 

// Function to compute Fibonacci numbers using dynamic programming
int fibonacci(int n) {
    int dp[n + 1]; // Array to store Fibonacci numbers

    // Base cases
    dp[0] = 0;
    dp[1] = 1;

    // Fill the dp array
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2]; // Fibonacci relation
    }

    return dp[n]; // Return the nth Fibonacci number
}

// Main function
int main() {
    int n;

    // Input the position in the Fibonacci sequence
    printf("Enter the position in the Fibonacci sequence: ");
    scanf("%d", &n);

    // Calculate the Fibonacci number at the given position
    int result = fibonacci(n);
    printf("Fibonacci number at position %d: %d\n", n, result);

    return 0;
}

Explanation of the Code

The program consists of two main parts: the function for calculating the Fibonacci number and the main function to handle input and output:

• The fibonacci function implements the dynamic programming approach:
  • An array dp is created to store the Fibonacci numbers from 0 to n.
  • The base cases are defined: dp[0] is 0 and dp[1] is 1.
  • The function iterates from 2 to n and fills in the array using the Fibonacci relation dp[i] = dp[i - 1] + dp[i - 2].
• The main function handles user input:
  • The user is prompted to enter the position in the Fibonacci sequence.
  • It calculates the Fibonacci number at the given position by calling the fibonacci function and displays the result.

Usage

To use the program:

1. Compile the program using a C compiler (e.g., gcc).
2. Run the executable and input the position in the Fibonacci sequence.
3. The program will output the Fibonacci number at that position.