Fibonacci (Bottom-up DP)

Compute the nth Fibonacci number by filling a table from the bottom up. Each entry depends only on its two predecessors — the textbook introduction to dynamic programming.

time O(n)

space O(n) table, O(1) with rolling vars

Input

Press Tab out of the box or click Resetto regenerate frames from the current input.

Visualization

No frames yet — edit input and click Run.

—

Pseudocode

dp[0] = 0
dp[1] = 1
for i in 2..n:
  dp[i] = dp[i-1] + dp[i-2]
return dp[n]