Memoization

Top-down DP with caching.

6 min readMastering Data Structures & Algorithms for Software Engineering InterviewsCode

Memoization Concept

Memoization = remembering results of expensive function calls. Cache return value for given inputs. On subsequent calls with same inputs, return cached result. Top-down approach: solve problem recursively, store subproblem results.

Fibonacci with Memoization

Gomemoized-fibonacci.go

31 linesLn 1, Col 1Go

Map for sparse keys, slice for dense 0..n keys. Check cache before computing. Reduces O(2^n) to O(n).

Generic Memoization

Helper function to memoize any function. Go generics (1.18+) enable type-safe memoization.

Gogeneric-memoize.go

17 linesLn 1, Col 1Go

Generic memoize wraps any function. Recursive calls go through memoized version via closure. Type-safe with generics.

Memoization vs Tabulation

Aspect	Memoization (Top-down)	Tabulation (Bottom-up)
Approach	Recursive + cache	Iterative + table
Space	Call stack + cache	Table only
Subproblems	Only computes needed	May compute extra
Code clarity	Matches recurrence	Requires ordering logic
Stack overflow	Risk for deep recursion	No risk
When to use	Sparse subproblems, natural recursion	Dense subproblems, iterative preferred

Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.