1 · Model, solve and test · 25 MIN
Dynamic programming with a rolling state
Dynamic programming with a rolling state
A recurrence can reuse earlier results rather than recomputing the same subproblem. Fibonacci depends only on the two previous values, so a rolling pair replaces a whole table. Define F(0)=0 and F(1)=1 before writing the loop. The contract limits n to 70 so each result remains a safe JavaScript integer. This avoids confusing algorithmic correctness with the language’s numeric representation limits.
After i loop iterations, previous should equal F(i).
Read the example
function solve(input){let previous=0,current=1;for(let i=0;i<input;i++){[previous,current]=[current,previous+current]}return previous}
console.log(JSON.stringify(solve(8)));Check the expected output
21
Your challenge
For an integer n from 0 through 70, return F(n), where F(0)=0, F(1)=1 and F(n)=F(n-1)+F(n-2).
Solution cost: O(n) additions within the bounded numeric contract. time · O(1) rolling values. space
Common trap
Naive recursion repeats overlapping work exponentially; a fast algorithm can still overflow its number type.