Program Explanation

The Fibonacci sequence is a series of numbers in which each number (after the first two) is the sum of
the two preceding ones. This program uses dynamic programming to compute Fibonacci numbers efficiently,
avoiding the exponential time complexity of the naive recursive approach.

Program Structure

1. Function Definition: The main function is fibonacci(n int) int, which
   takes an integer n as input and returns the n-th Fibonacci number.
2. Dynamic Programming Array: A 1D slice fib is created to store Fibonacci
   numbers up to n.
3. Initialization: The first two Fibonacci numbers (0 and 1) are initialized in the array.
4. Logic: A loop iterates from 2 to n:
   • Each Fibonacci number is calculated as the sum of the two preceding numbers.
5. Result: The function returns the value at index n of the array.

Go Code

package main

import (
    "fmt"
)

// fibonacci calculates the n-th Fibonacci number using dynamic programming.
func fibonacci(n int) int {
    if n < 0 {
        return -1 // Invalid input
    }
    if n == 0 {
        return 0 // Base case
    }
    if n == 1 {
        return 1 // Base case
    }

    // Create a DP array to store Fibonacci numbers
    fib := make([]int, n+1)
    fib[0], fib[1] = 0, 1 // Initialize the first two Fibonacci numbers

    // Fill the DP array
    for i := 2; i <= n; i++ {
        fib[i] = fib[i-1] + fib[i-2] // Calculate Fibonacci number
    }

    // Return the n-th Fibonacci number
    return fib[n]
}

func main() {
    // Example input
    n := 10
    
    result := fibonacci(n)
    fmt.Printf("The %d-th Fibonacci number is: %d\n", n, result)
}

Explanation of the Code:

• Function fibonacci(n int) int:
  • This function computes the n-th Fibonacci number using dynamic programming.
  • It initializes a 1D slice fib where fib[i] will store the i-th Fibonacci number.
• Dynamic Programming Array (fib):
  • The size of the fib array is n + 1 to accommodate Fibonacci numbers from 0 to n.
  • The first two Fibonacci numbers are set: fib[0] = 0 and fib[1] = 1.
• Logic for Filling the DP Array:
  • A loop iterates from 2 to n, calculating each Fibonacci number as the sum of the two preceding numbers:
    • fib[i] = fib[i-1] + fib[i-2].
• Result:
  • The function returns the n-th Fibonacci number located at fib[n].

How to Run the Program:

1. Save the code as main.go.
2. Open your terminal and navigate to the directory containing the file.
3. Run the command go run main.go.

This program effectively demonstrates the solution to computing Fibonacci numbers using dynamic programming, providing a clear and efficient method for obtaining results.

Conclusion

This Go program efficiently calculates the n-th Fibonacci number using dynamic programming, reducing
the time complexity to O(n). This method is useful in various applications, such as algorithm design
and optimization, where Fibonacci numbers play a crucial role.