Memoization Top Down DP in DSA Javascript - 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 result

↓

End

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

Execution Sample

DSA Javascript

function fib(n, memo = {}) {
  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];
}
console.log(fib(5));

Calculates Fibonacci number 5 using memoization to avoid repeated calculations.

Execution Table

Step	Operation	n	Memo Before	Recursive Calls	Memo After	Returned Value
1	Call fib(5)	5	{}	fib(4), fib(3)	{5:5}	5
2	Call fib(4)	4	{}	fib(3), fib(2)	{4:3}	3
3	Call fib(3)	3	{}	fib(2), fib(1)	{3:2}	2
4	Call fib(2)	2	{}	fib(1), fib(0)	{2:1}	1
5	Call fib(1)	1	{}	None	{}	1
6	Call fib(0)	0	{}	None	{}	0
7	Return fib(2)	2	{}	None	{2:1}	1
8	Return fib(3)	3	{2:1}	None	{3:2}	2
9	Return fib(4)	4	{3:2,2:1}	None	{4:3}	3
10	Return fib(5)	5	{4:3,3:2,2:1}	None	{5:5}	5

💡 fib(5) returns 5 after all recursive calls use memoized results to avoid recomputation.

Variable Tracker

Variable	Start	After Step 5	After Step 7	After Step 9	Final
n	5	2	2	4	5
memo	{}	{}	{2:1}	{4:3,3:2,2:1}	{5:5,4:3,3:2,2:1}
Returned Value	N/A	1	1	3	5

Key Moments - 3 Insights

Why do we check if memo[n] exists before computing fib(n)?

Because if memo[n] exists, it means we already computed fib(n) before, so we can return it immediately without repeating the recursive calls. See Step 2 and Step 3 where memo is checked to avoid recomputation.

What happens when n is 1 or 0 in the recursion?

These are base cases that return n directly without recursion. This stops the recursion from going infinitely. See Steps 5 and 6 where fib(1) and fib(0) return 1 and 0 respectively.

How does memoization improve performance here?

Memoization saves results of fib(n) in the memo object. Later calls reuse these saved results instead of recalculating. This reduces exponential calls to linear. See how memo grows from empty to full by Step 10.

Visual Quiz - 3 Questions

Look at the execution table, what is the value of memo after Step 7?

A {}

B {"2":1}

C {"3":2}

D {"5":5}

💡 Hint

Check the 'Memo After' column in Step 7 of the execution table.

At which step does fib(3) return its computed value?

A Step 3

B Step 5

C Step 8

D Step 10

💡 Hint

Look at the 'Returned Value' column and find when fib(3) returns.

If we remove the memo check, what would happen to the number of recursive calls?

A It would increase exponentially

B It would stay the same

C It would decrease

D It would become zero

💡 Hint

Memoization avoids repeated calls; without it, calls grow exponentially.

Concept Snapshot

Memoization Top Down DP:
- Use recursion with a memo object to save results.
- Check memo before computing to avoid repeats.
- Base cases stop recursion.
- Store computed results in memo.
- Returns saved results for faster performance.

Full Transcript

Memoization in top-down dynamic programming means saving results of recursive calls in a memo object. When the function is called with a value, it first checks if the result is already in memo. If yes, it returns that result immediately. If not, it computes the result recursively, stores it in memo, and then returns it. This avoids repeated calculations and speeds up the program. For example, in Fibonacci calculation, base cases for n=0 or n=1 return immediately. Recursive calls build up memo with results for each n. This way, each Fibonacci number is computed once and reused. The execution table shows each step, the state of memo, and returned values. Key moments include understanding why memo is checked first, the role of base cases, and how memoization improves performance. The visual quiz tests understanding of memo state, return steps, and effect of removing memoization.

Practice

1. What is the main purpose of memoization in top-down dynamic programming?

easy

A. To store results of subproblems to avoid repeated calculations

B. To sort the input data before processing

C. To convert recursive code into iterative code

D. To reduce the memory usage by deleting variables

Solution

1. Step 1: Understand memoization concept

   Memoization saves the results of expensive function calls and returns the cached result when the same inputs occur again.

2. Step 2: Identify its role in top-down DP

   In top-down dynamic programming, memoization prevents repeated calculations of the same subproblems by storing their results.

3. Final Answer:

   To store results of subproblems to avoid repeated calculations -> Option A

4. Quick Check:

   Memoization = Store subproblem results [OK]

Hint: Memoization caches answers to reuse later [OK]

Common Mistakes:

• Confusing memoization with sorting
• Thinking memoization reduces memory usage
• Believing memoization converts recursion to iteration

2. Which of the following is the correct way to declare a memo object in JavaScript for top-down DP?

easy

A. const memo = 0;

B. let memo = [];

C. const memo = new Map();

D. var memo = function() {};

Solution

1. Step 1: Identify memo storage type

   Memoization requires a data structure to store key-value pairs of subproblem results. Map is ideal for this in JavaScript.

2. Step 2: Check options for correct syntax

   const memo = new Map(); uses new Map() which is correct. let memo = []; is an array, which can work but less flexible. var memo = function() {}; is a function, incorrect. const memo = 0; is a number, incorrect.

3. Final Answer:

   const memo = new Map(); -> Option C

4. Quick Check:

   Memo object = Map() [OK]

Hint: Use Map() for flexible memo keys [OK]

Common Mistakes:

• Using a function instead of an object
• Initializing memo as a number
• Confusing array with Map for memo

3. What will be the output of the following JavaScript code using memoization for Fibonacci?

const memo = new Map();
function fib(n) {
  if (n <= 1) return n;
  if (memo.has(n)) return memo.get(n);
  const result = fib(n - 1) + fib(n - 2);
  memo.set(n, result);
  return result;
}
console.log(fib(5));

medium

A. 5

B. 8

C. 3

D. 13

Solution

1. Step 1: Understand Fibonacci sequence

   Fibonacci sequence starts as 0,1,1,2,3,5,8,... So fib(5) = 5.

2. Step 2: Trace the code execution

   The function uses memoization to avoid repeated calls. fib(5) calculates fib(4)+fib(3), and so on, finally returning 5.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   fib(5) = 5 [OK]

Hint: Recall Fibonacci sequence values [OK]

Common Mistakes:

• Confusing fib(5) with fib(6)
• Ignoring base cases
• Not understanding memo usage

4. Identify the bug in this memoized factorial function and select the fix:

const memo = {};
function factorial(n) {
  if (n === 0) return 1;
  if (memo[n]) return memo[n];
  memo[n] = n * factorial(n - 1);
  return memo[n];
}
console.log(factorial(5));

medium

A. Change base case to 'if (n === 1) return 1;'

B. Change 'if (memo[n])' to 'if (memo.hasOwnProperty(n))'

C. Initialize memo as 'const memo = new Map();'

D. Remove memo and use plain recursion

Solution

1. Step 1: Understand the bug in memo check

   Using 'if (memo[n])' fails when memo[n] is 0 or falsy. It should check if the key exists.

2. Step 2: Fix by checking key existence

   Using 'memo.hasOwnProperty(n)' correctly checks if the result is stored, avoiding false negatives.

3. Final Answer:

   Change 'if (memo[n])' to 'if (memo.hasOwnProperty(n))' -> Option B

4. Quick Check:

   Check key existence, not truthiness [OK]

Hint: Check key presence, not value truthiness [OK]

Common Mistakes:

• Checking memo[n] directly causes bugs for 0 or falsy values
• Changing base case unnecessarily
• Removing memo defeats purpose

5. Given the following top-down memoized function to count ways to climb stairs, what is the output of countWays(4)?

const memo = {};
function countWays(n) {
  if (n === 0) return 1;
  if (n < 0) return 0;
  if (memo.hasOwnProperty(n)) return memo[n];
  memo[n] = countWays(n - 1) + countWays(n - 2);
  return memo[n];
}
console.log(countWays(4));

hard

A. 7

B. 6

C. 8

D. 5

Solution

1. Step 1: Understand the problem

   This function counts ways to climb stairs taking 1 or 2 steps. Base cases: countWays(0)=1, countWays(negative)=0.

2. Step 2: Calculate countWays(4) step-by-step

   countWays(4) = countWays(3) + countWays(2) countWays(3) = countWays(2) + countWays(1) countWays(2) = countWays(1) + countWays(0) countWays(1) = countWays(0) + countWays(-1) countWays(0) = 1, countWays(-1) = 0 So countWays(1) = 1 + 0 = 1 countWays(2) = 1 + 1 = 2 countWays(3) = 2 + 1 = 3 countWays(4) = 3 + 2 = 5

3. Final Answer:

   5 -> Option D

4. Quick Check:

   Ways to climb 4 stairs = 5 [OK]

Hint: Count ways as sum of previous two counts [OK]

Common Mistakes:

• Miscounting base cases
• Forgetting negative input returns 0
• Mixing up addition order