Beginner LevelData Structures & Algorithms
What is the difference between Memoization (Top-Down DP) and Tabulation (Bottom-Up DP)?
ā Interview Prompt: Compare Top-Down Memoization vs Bottom-Up Tabulation Dynamic Programming using the Fibonacci sequence as an example.
Both techniques optimise overlapping sub-problems from $O(2^N)$ recursive brute-force to $O(N)$.
Memoization (Top-Down):
ā¢
Recursive approach + caching computed results in a memo table.
ā¢
Computes only the sub-problems actually needed.
ā¢
$O(N)$ time, $O(N)$ space (memo table + call stack).
Tabulation (Bottom-Up):
ā¢
Iteratively fills a table starting from the smallest sub-problems.
ā¢
No recursion ā no stack overflow risk.
ā¢
$O(N)$ time, $O(N)$ space (reducible to $O(1)$ by keeping only the last 2 values).
Code Implementation Example
typescript
// Memoization ā Top-Down
function fibMemo(n: number, memo = new Map<number, number>()): number {
if (n <= 1) return n;
if (memo.has(n)) return memo.get(n)!;
const result = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
memo.set(n, result);
return result;
}
// Tabulation ā Bottom-Up, O(1) space
function fibTab(n: number): number {
if (n <= 1) return n;
let prev2 = 0, prev1 = 1;
for (let i = 2; i <= n; i++) {
[prev2, prev1] = [prev1, prev1 + prev2];
}
return prev1;
}š”Fibonacci via Memoization (top-down) and Tabulation (bottom-up O(1) space).
šÆ Interview Key Takeaway
Memoization is easier to implement from recursive solutions. Tabulation avoids stack overhead and can often reduce space from O(N) to O(1).
#DSA#Dynamic Programming#Memoization#Tabulation#Beginner
Back to all Data Structures & Algorithms Questionsā