LeetCode 509 Fibonacci - Tabulation Implementation

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 $2$ to $n$, 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.

Time: $O(n)$. Space: $O(n)$.