Math Dynamic Programming Memoization Tabulation
Learner Level

Implement the fibonacciDP method that returns the nth Fibonacci number using dynamic programming.

The input contains an integer n. Your task is to return the nth Fibonacci number.

The Fibonacci sequence starts with F(0) = 0 and F(1) = 1. Every next value is the sum of the previous two values. For example, F(6) is 8.

Example 1
Input:
n (int) = 0
Return:
(int) 0
Example 2
Input:
n (int) = 6
Return:
(int) 8
Example 3
Input:
n (int) = 8
Return:
(int) 21

Use dynamic programming to build the Fibonacci value from the bottom up.

Instead of using recursion, keep the previous two Fibonacci values and calculate the next value in a loop. This avoids repeated calculations and uses only constant extra space.

Pseudocode:

function fibonacciDP(n):
    if n == 0:
        return 0
    prev2 = 0
    prev1 = 1
    for i from 2 to n:
        current = prev1 + prev2
        prev2 = prev1
        prev1 = current
    return prev1
Run your code to see the result.