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 computed result

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, 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 memoization to avoid repeated calculations.

Execution Table

Step	Operation	n	Memo Before	Recursive Calls	Memo After	Returned Value
1	fib(4) called	4	[-1,-1,-1,-1,-1]	fib(3), fib(2)	[-1,-1,-1,-1,-1]	pending
2	fib(3) called	3	[-1,-1,-1,-1,-1]	fib(2), fib(1)	[-1,-1,-1,-1,-1]	pending
3	fib(2) called	2	[-1,-1,-1,-1,-1]	fib(1), fib(0)	[-1,-1,-1,-1,-1]	pending
4	fib(1) called	1	[-1,-1,-1,-1,-1]	none	[-1,-1,-1,-1,-1]	1
5	fib(0) called	0	[-1,-1,-1,-1,-1]	none	[-1,-1,-1,-1,-1]	0
6	fib(2) memoized	2	[-1,-1,-1,-1,-1]	none	[-1,-1,1,-1,-1]	1
7	fib(1) called again	1	[-1,-1,1,-1,-1]	none	[-1,-1,1,-1,-1]	1
8	fib(3) memoized	3	[-1,-1,1,-1,-1]	none	[-1,-1,1,2,-1]	2
9	fib(2) called again	2	[-1,-1,1,2,-1]	none	[-1,-1,1,2,-1]	1
10	fib(4) memoized	4	[-1,-1,1,2,-1]	none	[-1,-1,1,2,3]	3
11	Return final result	4	[-1,-1,1,2,3]	none	[-1,-1,1,2,3]	3

💡 fib(4) returns 3 after all recursive calls and memoization complete

Variable Tracker

Variable	Start	After Step 6	After Step 8	After Step 10	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 can return it immediately without repeating work. See steps 7 and 9 where memoized values are reused.

What happens when n is 0 or 1?

These are base cases returning n directly without recursion, as shown in steps 4 and 5. This stops infinite recursion.

Why do recursive calls reduce n by 1 and 2?

Because Fibonacci number fib(n) depends on fib(n-1) and fib(n-2). The recursion breaks the problem into smaller subproblems, as seen in steps 1-3.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of memo after step 8?

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

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

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

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

💡 Hint

Check the 'Memo After' column in row with Step 8

At which step does fib(2) get its value memoized for the first time?

A Step 3

B Step 9

C Step 6

D Step 10

💡 Hint

Look for when memo[2] changes from -1 to 1 in the 'Memo After' column

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

A It would decrease

B It would increase drastically

C It would stay the same

D It would stop immediately

💡 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
- Base cases return directly
- Store computed results in memo
- Return memoized or computed value

Full Transcript

Memoization Top Down DP solves problems by breaking them into smaller parts recursively. Before computing a result, it checks if the answer is already saved in a memo array. If yes, it returns that saved answer immediately. If no, it computes the result recursively, saves it in memo, then returns it. This avoids repeated work and speeds up the program. Base cases stop recursion. For example, Fibonacci numbers use this method by saving fib(n) once computed. 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 convert recursive code into iterative code

B. To sort the input data before processing

C. To store results of subproblems to avoid repeated calculations

D. To increase the number of recursive calls

Solution

1. Step 1: Understand memoization concept

   Memoization saves answers of smaller problems so they don't get solved again.

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

   It stores subproblem results during recursion to speed up the process.

3. Final Answer:

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

4. Quick Check:

   Memoization = Store subproblem results [OK]

Hint: Memoization means saving answers to reuse later [OK]

Common Mistakes:

• Confusing memoization with sorting
• Thinking memoization converts recursion to iteration
• Believing memoization increases recursive calls

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

easy

A. int memo[] = new int[100];

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

C. int memo = new int[100];

D. int memo(100);

Solution

1. Step 1: Recall C array declaration syntax

   In C, arrays are declared with fixed size and optional initialization like int memo[100] = {0};

2. Step 2: Check each option

   int memo[100] = {0}; uses correct C syntax. Options A and C use Java/C++ style. int memo(100); is invalid in C.

3. Final Answer:

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

4. Quick Check:

   C array declaration = int memo[100] = {0}; [OK]

Hint: C arrays use fixed size with square brackets [OK]

Common Mistakes:

• Using Java or C++ style array declarations in C
• Forgetting to initialize memo array to zero
• Using parentheses instead of brackets for arrays

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

int memo[10] = {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() {
  printf("%d", fib(5));
  return 0;
}

medium

A. 0

B. 8

C. 3

D. 5

Solution

1. Step 1: Trace fib(5) calls and memo usage

   fib(5) calls fib(4) + fib(3), and so on. Memo stores results to avoid repeats.

2. Step 2: Calculate fib(5)

   fib(0)=0, fib(1)=1, fib(2)=1, fib(3)=2, fib(4)=3, fib(5)=5.

3. Final Answer:

   5 -> Option D

4. Quick Check:

   fib(5) = 5 [OK]

Hint: Remember Fibonacci sequence: 0,1,1,2,3,5... [OK]

Common Mistakes:

• Confusing fib(5) with fib(6)
• Ignoring memoization effect
• Assuming memo array starts with all ones

4. Identify the error in this memoized Fibonacci function in C:

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

int main() {
  printf("%d", fib(5));
  return 0;
}

medium

A. memo array is not initialized to -1

B. fib function should return void

C. Base case should be n == 0 only

D. memo array size is too small

Solution

1. Step 1: Check memo array initialization

   Memo is checked for -1 but never initialized, so contains garbage values.

2. Step 2: Understand impact on memoization

   Without initialization, memo[n] != -1 may be true incorrectly, causing wrong returns.

3. Final Answer:

   memo array is not initialized to -1 -> Option A

4. Quick Check:

   Initialize memo to -1 before use [OK]

Hint: Always initialize memo array before use [OK]

Common Mistakes:

• Forgetting to initialize memo array
• Changing base case incorrectly
• Assuming default zero initialization in C

5. Given the following top-down memoized code to count ways to climb stairs (1 or 2 steps), what is the output of countWays(4)? Assume memo array is initialized with -1.

int memo[100];
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() {
  for(int i=0; i<100; i++) memo[i] = -1;
  printf("%d", countWays(4));
  return 0;
}

hard

A. 5

B. 7

C. 8

D. 4

Solution

1. Step 1: Understand problem and base cases

   Ways to climb 0 steps = 1, negative steps = 0, ways(n) = ways(n-1)+ways(n-2).

2. Step 2: Calculate countWays(4)

   countWays(1)=1, countWays(2)=2, countWays(3)=3, countWays(4)=5.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   Ways to climb 4 steps = 5 [OK]

Hint: Count ways follow Fibonacci pattern starting with 1,1 [OK]

Common Mistakes:

• Confusing base cases for counting ways
• Not initializing memo array
• Mixing up countWays with Fibonacci values