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) =
0Returns (int)
0Example 2
Input
n (int) =
6Returns (int)
8Example 3
Input
n (int) =
8Returns (int)
21Use 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 prev1Ready to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run