Memoization Top Down DP in DSA C++ - 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

↓

Combine results to solve original problem

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

Execution Sample

DSA C++

int fib(int n, vector<int>& memo) {
  if (n <= 1) return n;
  if (memo[n] != -1) return memo[n];
  memo[n] = fib(n-1, memo) + fib(n-2, memo);
  return memo[n];
}

This code computes Fibonacci numbers using top-down memoization to avoid repeated work.

Execution Table

Step	Operation	n	Memo Before	Recursive Calls	Memo After	Returned Value
1	Call fib(4)	4	[-1, -1, -1, -1, -1]	fib(3), fib(2)	[-1, -1, -1, -1, -1]	pending
2	Call fib(3)	3	[-1, -1, -1, -1, -1]	fib(2), fib(1)	[-1, -1, -1, -1, -1]	pending
3	Call fib(2)	2	[-1, -1, -1, -1, -1]	fib(1), fib(0)	[-1, -1, -1, -1, -1]	pending
4	Call fib(1)	1	[-1, -1, -1, -1, -1]	None	[-1, -1, -1, -1, -1]	1
5	Call fib(0)	0	[-1, -1, -1, -1, -1]	None	[-1, -1, -1, -1, -1]	0
6	Compute fib(2)	2	[-1, -1, -1, -1, -1]	fib(1)+fib(0)=1+0	[-1, -1, 1, -1, -1]	1
7	Return fib(2)	2	[-1, -1, 1, -1, -1]	None	[-1, -1, 1, -1, -1]	1
8	Call fib(1)	1	[-1, -1, 1, -1, -1]	None	[-1, -1, 1, -1, -1]	1
9	Compute fib(3)	3	[-1, -1, 1, -1, -1]	fib(2)+fib(1)=1+1	[-1, -1, 1, 2, -1]	2
10	Return fib(3)	3	[-1, -1, 1, 2, -1]	None	[-1, -1, 1, 2, -1]	2
11	Call fib(2)	2	[-1, -1, 1, 2, -1]	None	[-1, -1, 1, 2, -1]	1 (memo hit)
12	Compute fib(4)	4	[-1, -1, 1, 2, -1]	fib(3)+fib(2)=2+1	[-1, -1, 1, 2, 3]	3
13	Return fib(4)	4	[-1, -1, 1, 2, 3]	None	[-1, -1, 1, 2, 3]	3
14	End	-	[-1, -1, 1, 2, 3]	No more calls	[-1, -1, 1, 2, 3]	3

💡 All recursive calls completed and results stored in memo; final fib(4) = 3 returned.

Variable Tracker

Variable	Start	After Step 6	After Step 9	After Step 12	Final
n	4	2	3	4	4
memo	[-1, -1, -1, -1, -1]	[-1, -1, 1, -1, -1]	[-1, -1, 1, 2, -1]	[-1, -1, 1, 2, 3]	[-1, -1, 1, 2, 3]
Returned Value	pending	1	2	3	3

Key Moments - 3 Insights

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

Because if memo[n] is not -1, it means fib(n) was already computed and saved, so we return it immediately to avoid repeated work. See step 11 where a memo hit happens.

Why do we store the result in memo after computing fib(n)?

Storing the result in memo lets future calls reuse the answer without recomputing. This is shown in steps 6, 9, and 12 where memo updates happen.

What happens when n is 0 or 1?

These are base cases returning n directly without recursion or memo. See steps 4 and 5 where fib(1) and fib(0) return immediately.

Visual Quiz - 3 Questions

Look at the execution table, what is the value of memo after step 9?

A [-1, -1, -1, -1, -1]

B [-1, -1, 1, -1, -1]

C [-1, -1, 1, 2, -1]

D [-1, -1, 1, 2, 3]

💡 Hint

Check the 'Memo After' column at step 9 in the execution_table.

At which step does fib(2) get computed and stored in memo for the first time?

A Step 6

B Step 3

C Step 8

D Step 11

💡 Hint

Look for the first memo update for n=2 in the execution_table.

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

A They would stay the same

B They would increase

C They would decrease

D No recursive calls would happen

💡 Hint

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

Concept Snapshot

Memoization Top Down DP:
- Use recursion with a memo array to save results.
- Check memo before computing to avoid repeats.
- Store computed results in memo.
- Base cases return directly.
- Speeds up exponential problems to linear time.

Full Transcript

Memoization in top-down dynamic programming means solving a problem by breaking it into smaller subproblems recursively, but saving each subproblem's answer in a memo array. When the function is called again with the same input, it returns the saved answer instead of recomputing. For example, in Fibonacci, fib(n) calls fib(n-1) and fib(n-2). Without memo, calls repeat many times. With memo, each fib(n) is computed once and saved. The flow is: check memo, if found return it, else compute recursively, save in memo, then return. Base cases like fib(0) and fib(1) return immediately. This approach reduces exponential time to linear time. The execution table shows each call, memo state before and after, and returned values step by step.

Practice

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

easy

A. To reduce the memory usage by deleting variables

B. To sort the input data before processing

C. To store results of subproblems to avoid repeated calculations

D. To convert recursive code into iterative code

Solution

1. Step 1: Understand memoization concept

   Memoization saves the results of subproblems so they are not recalculated.

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

   In top-down DP, memoization avoids repeated work by caching answers.

3. Final Answer:

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

4. Quick Check:

   Memoization = store subproblem results [OK]

Hint: Memoization caches answers to speed up recursion [OK]

Common Mistakes:

• Confusing memoization with sorting
• Thinking memoization reduces memory by deleting variables
• Believing memoization converts recursion to iteration

2. Which of the following is the correct way to declare a memo array for Fibonacci numbers in C++?

easy

A. int memo[1000];

B. int memo[1000] = {0};

C. int memo[] = new int[1000];

D. int memo(1000, 0);

Solution

1. Step 1: Check array initialization

   int memo[1000] = {0}; declares an array of size 1000 and initializes all elements to 0.

2. Step 2: Compare other options

   int memo[1000]; declares but does not initialize; C is invalid syntax in C++; D is invalid syntax for array.

3. Final Answer:

   int memo[1000] = {0}; -> Option B

4. Quick Check:

   Correct array declaration with initialization = int memo[1000] = {0}; [OK]

Hint: Initialize memo array with zeros to mark unvisited [OK]

Common Mistakes:

• Not initializing memo array causing garbage values
• Using invalid syntax for array declaration
• Confusing vector initialization with array

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

int memo[100] = {0};
int fib(int n) {
  if (n <= 1) return n;
  if (memo[n] != 0) return memo[n];
  memo[n] = fib(n-1) + fib(n-2);
  return memo[n];
}
int main() {
  std::cout << fib(5);
  return 0;
}

medium

A. 5

B. 8

C. 3

D. 0

Solution

1. Step 1: Trace fib(5) calls

   fib(5) = fib(4) + fib(3), fib(4) = 3, fib(3) = 2, so fib(5) = 5.

2. Step 2: Confirm memoization usage

   Memo stores results to avoid repeated calls but does not change output.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   fib(5) = 5 [OK]

Hint: Remember fib(5) = 5 in Fibonacci sequence [OK]

Common Mistakes:

• Confusing fib(5) with fib(6)
• Ignoring base cases n <= 1
• Assuming memo array starts with all zeros means zero output

4. Identify the error in this memoized Fibonacci function:

int memo[100] = {0};
int fib(int n) {
  if (n == 0) return 0;
  if (n == 1) return 1;
  if (memo[n] != 0) return memo[n];
  memo[n] = fib(n-1) + fib(n-2);
  return memo[n];
}

medium

A. No error, code works correctly

B. Memo array initialization is incorrect

C. fib(2) returns wrong value due to memo check

D. Base case for n == 0 is missing

Solution

1. Step 1: Trace fib(2)

   fib(2) calls fib(1) and fib(0), returns 1 + 0 = 1 correctly, memo[2] = 1.

2. Step 2: Check memo condition

   Base cases are before memo check, so fib(0)=0 and fib(1)=1 always handled directly. For n>=2, fib(n) > 0.

3. Step 3: No error present

   Code produces correct results; using -1 init is better practice generally but not required here.

4. Final Answer:

   No error, code works correctly -> Option A

5. Quick Check:

   fib(2) = 1 correctly [OK]

Hint: Use a special value (e.g., -1) to mark unvisited memo entries [OK]

Common Mistakes:

• Assuming zero means unvisited memo entry
• Not handling base cases properly in memoization
• Ignoring that fib(0) = 0 causes memo check issues

5. Given the following top-down memoized code for counting ways to climb stairs (1 or 2 steps), what is the output of countWays(4)?

int memo[100] = {-1};
int countWays(int n) {
  if (n == 0) return 1;
  if (n < 0) return 0;
  if (memo[n] != -1) return memo[n];
  memo[n] = countWays(n-1) + countWays(n-2);
  return memo[n];
}
int main() {
  std::cout << countWays(4);
  return 0;
}

hard

A. 6

B. 7

C. 8

D. 5

Solution

1. Step 1: Understand problem and base cases

   countWays(0) = 1 means one way to stand still; countWays(n) sums ways from n-1 and n-2 steps.

2. Step 2: Calculate countWays(4)

   countWays(4) = countWays(3) + countWays(2) countWays(3) = countWays(2) + countWays(1) countWays(2) = countWays(1) + countWays(0) countWays(1) = countWays(0) + countWays(-1) = 1 + 0 = 1 countWays(0) = 1 So, 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 by summing previous two counts [OK]

Common Mistakes:

• Forgetting base case countWays(0) = 1
• Miscounting negative step returns
• Not initializing memo with -1 to mark unvisited