Can you implement a function to compute the nth number in the Fibonacci sequence using dynamic programming?

Computing the nth Fibonacci number using dynamic programming is pretty straightforward, you just need to store each Fibonacci number as you compute it and use previously computed numbers to compute the next ones.

Here is a simple Python implementation:

def fib(n):
    F = [0, 1] + [0]*(n-1)
    for i in range(2, n+1):
        F[i] = F[i-1] + F[i-2]
    return F[n]

This function creates an empty list ‘F‘ of size ‘n+1‘ and initializes ‘F[0]‘ and ‘F[1]‘ to ‘0‘ and ‘1‘ respectively. After that, it computes each ‘F[i]‘ as ‘F[i-1] + F[i-2]‘ for ‘i = 2‘ to ‘n‘.

This approach allows it to calculate the nth Fibonacci number in O(n) time, which is much better than the naive recursive solution that takes O(2ⁿ) time.

We can also optimize this function by only keeping the last two previously computed Fibonacci numbers:

def fib(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a+b
    return a

This version of the function computes the nth Fibonacci number in O(n) time and O(1) space.

If you’re interested in mathematical representations, here’s a brief overview:

The Fibonacci sequence is formally defined by the recurrence relation:

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

with ‘F(0) = 0‘ and ‘F(1) = 1‘. Hence, the formula used in the dynamic programming-based implementations is ‘F[i] = F[i-1] + F[i-2]‘ for ‘i = 2‘ to ‘n‘.