Stage 1 · Code
Dynamic Programming
Fibonacci
Classic DP intro: recursive, memoized, tabulated, O(1) space.
5 min readMastering Data Structures & Algorithms for Software Engineering InterviewsCode
Naive Recursive
Goexponential-recursive.go
6 linesLn 1, Col 1Go
Exponential due to recomputing same subproblems. Recursion tree has 2^n nodes.
Memoized
Gomemoized-o(n).go
14 linesLn 1, Col 1Go
Cache results. Each value computed once. Slice for dense integer keys.
Tabulated
Gobottom-up-o(n)-time,-o(n)-space.go
10 linesLn 1, Col 1Go
Iterative, no recursion overhead. Fill table from base cases up.
Space Optimized
Goo(1)-space.go
9 linesLn 1, Col 1Go
Only need last two values. Shift variables each iteration. Most efficient for single query.
Matrix Exponentiation
Fibonacci via matrix power: [[1,1],[1,0]]^n gives F(n+1), F(n). O(log n) via fast exponentiation.
Goo(log-n)-fibonacci.go
27 linesLn 1, Col 1Go
Fast exponentiation by squaring. O(log n) multiplications. Useful for many queries or very large n.
Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.