AlgoScope

Fibonacci

f(n) = f(n-1) + f(n-2). The smallest example of memoization versus tabulation.

Dynamic programming, algorithm, beginner
Index 2 is 1 plus 0, which is 1.001112345678910i

DP in One Row: Fibonacci by table

Decision, step 2 of 11

dp[2] = dp[1] + dp[0] = 1 + 0 = 1.

Cost

Best
O(n)
Average
O(n)
Worst
O(n)
Space
O(1)

O(2^n) naive. O(n) memoized. O(1) space with two variables.

Leads to

Topics that need this one first.

Taught by the same lesson

DP in One Row covers these too, in the same run.