Memoization Top Down DP in DSA Typescript - Execution Trace

Concept Flow - Memoization Top Down DP

Start with problem input

↓

Check if result in memo?

Yes→Return memoized result

No↓

Compute result recursively

↓

Store result in memo

↓

Return computed result

The flow starts by checking if the answer is already saved (memo). If yes, return it. If no, compute recursively, save it, then return.

Execution Sample

DSA Typescript

function fib(n: number, memo: number[] = []): number {
  if (n <= 1) return n;
  if (memo[n] !== undefined) return memo[n];
  memo[n] = fib(n-1, memo) + fib(n-2, memo);
  return memo[n];
}

Calculates Fibonacci number n using top-down memoization to avoid repeated work.

Execution Table

Step	Operation	n	Memo Before	Recursive Calls	Memo After	Returned Value
1	fib(4) called	4	[]	fib(3), fib(2)	[empty]	pending
2	fib(3) called	3	[]	fib(2), fib(1)	[empty]	pending
3	fib(2) called	2	[]	fib(1), fib(0)	[empty]	pending
4	fib(1) base case	1	[]	none	[empty]	1
5	fib(0) base case	0	[]	none	[empty]	0
6	fib(2) computed	2	[]	fib(1)=1, fib(0)=0	[, , 1]	1
7	fib(1) base case	1	[, , 1]	none	[, , 1]	1
8	fib(3) computed	3	[, , 1]	fib(2)=1, fib(1)=1	[, , 1, 2]	2
9	fib(2) memo hit	2	[, , 1, 2]	none	[, , 1, 2]	1
10	fib(4) computed	4	[, , 1, 2]	fib(3)=2, fib(2)=1	[, , 1, 2, 3]	3
11	Return final result	4	[, , 1, 2, 3]	none	[, , 1, 2, 3]	3

💡 All recursive calls resolved and memo filled; final result fib(4) = 3 returned.

Variable Tracker

Variable	Start	After Step 6	After Step 8	After Step 10	Final
n	4	2	3	4	4
memo	[]	[, , 1]	[, , 1, 2]	[, , 1, 2, 3]	[, , 1, 2, 3]
Returned Value	pending	1	2	3	3

Key Moments - 3 Insights

Why do we check if memo[n] is defined before computing?

Because if memo[n] exists, it means we already computed fib(n). We return it immediately to avoid repeating work, as shown in steps 9 and 10 where fib(2) is returned from memo.

What happens when n is 0 or 1?

These are base cases that return n directly without recursion, as in steps 4 and 5. This stops infinite recursion and starts building answers up.

How does memoization reduce the number of recursive calls?

Memoization saves results so repeated calls like fib(2) in step 9 return instantly from memo instead of recomputing, drastically reducing calls.

Visual Quiz - 3 Questions

Look at the execution table at step 6. What is the memo array after computing fib(2)?

A [, , 2]

B [, , 1]

C [1, 1]

D []

💡 Hint

Check the 'Memo After' column at step 6 in the execution table.

At which step does the function return the final result for fib(4)?

A Step 8

B Step 10

C Step 11

D Step 9

💡 Hint

Look for the step where 'Returned Value' is 3 and no further recursive calls happen.

If memoization was not used, how would the number of recursive calls change?

A They would increase because repeated calls are not cached.

B They would decrease because memoization adds overhead.

C They would stay the same.

D They would stop immediately.

💡 Hint

Refer to the 'Recursive Calls' column and how memo hits avoid calls.

Concept Snapshot

Memoization Top Down DP:
- Use recursion with a memo (cache) to save results.
- Check memo before computing to avoid repeats.
- Base cases return direct answers.
- Store computed results in memo.
- Return memoized or computed result.
- Greatly reduces repeated work in overlapping subproblems.

Full Transcript

Memoization in top-down dynamic programming means saving results of recursive calls in a memo array. When the function is called with a parameter n, it first checks if the answer is already in memo. If yes, it returns that answer immediately. If not, it computes the answer recursively, stores it in memo, and returns it. Base cases like n=0 or n=1 return immediately without recursion. This approach avoids repeated calculations of the same subproblems, making the algorithm efficient. The example traced is Fibonacci number calculation for n=4, showing how memo fills step-by-step and recursive calls reduce.