Here's the bottom-up tabulation approach for Fibonacci:
function fib(n)
if n ≤ 1 then
return n
dp := array of size (n + 1)
dp[0] := 0
dp[1] := 1
for i from 2 to n
dp[i] := dp[i - 1] + dp[i - 2]
return dp[n]
You create an array dp where dp[i] stores fib(i). You initialize base cases, then loop from to , filling in each entry. No recursion, no call stack, just a simple loop.
The implementation follows directly from the recurrence. Each line of code corresponds to part of the mathematical formula. Walk through a small example step by step to verify your understanding.
Time: . Space: .