Fibonacci Numbers

December 22, 2023

Problem #

Given an integer n, find the nth Fibonacci number using dynamic programming. The first two Fibonacci numbers are 0 and 1, and each subsequent number is the sum of the previous two.

Solution #

The Python code to find the nth Fibonacci number using dynamic programming is as follows:

def fibonacci(n):
    # Initialize a list to store the Fibonacci numbers up to n
    fib_sequence = [0, 1]

    # Dynamic programming approach
    for i in range(2, n + 1):
        next_fib = fib_sequence[i - 1] + fib_sequence[i - 2]
        fib_sequence.append(next_fib)

    return fib_sequence[n]

# Example usage
n = 10  # for example, finding the 10th Fibonacci number
nth_fibonacci_number = fibonacci(n)

When this function is executed with n = 10, it returns 55, which is the 10th number in the Fibonacci sequence.