Memoization Top Down DP in DSA C# - Execution Trace

Concept Flow - Memoization Top Down DP

Start with problem input

↓

Check if result in memo

↓

Return memo

↓

Store result in memo

↓

Return result

Start with input, check if answer is saved. If yes, return it. If no, compute recursively, save answer, 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];
}

Computes Fibonacci number n using 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	Call Fib(1)	1	[-1, -1, 1, -1, -1]	None	[-1, -1, 1, -1, -1]	1
8	Compute Fib(3)	3	[-1, -1, 1, -1, -1]	Fib(2)+Fib(1)=1+1	[-1, -1, 1, 2, -1]	2
9	Call Fib(2)	2	[-1, -1, 1, 2, -1]	Memo hit	[-1, -1, 1, 2, -1]	1
10	Compute Fib(4)	4	[-1, -1, 1, 2, -1]	Fib(3)+Fib(2)=2+1	[-1, -1, 1, 2, 3]	3
11	Return final result	4	[-1, -1, 1, 2, 3]	None	[-1, -1, 1, 2, 3]	3

💡 All recursive calls resolved and memo filled, final 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, -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	N/A	1	2	3	3

Key Moments - 3 Insights

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

Checking memo[n] (see step 9) avoids repeating work by returning stored results immediately, saving time.

What happens when n is 0 or 1?

At steps 4 and 5, base cases return n directly without recursion, stopping further calls.

How does memoization improve performance here?

Memoization stores results (steps 6,8,10) so repeated calls like Fib(2) reuse stored values instead of recalculating.

Visual Quiz - 3 Questions

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

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

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

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

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

💡 Hint

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

At which step does the function first return a value without recursion?

A Step 1

B Step 6

C Step 4

D Step 9

💡 Hint

Look for steps where 'Recursive Calls' is 'None' and a value is returned.

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

A Calls would increase

B Calls would decrease

C Calls would stay the same

D Calls would stop immediately

💡 Hint

Memoization avoids repeated calls; without it, repeated calls increase 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 parts recursively, but saving each result in a memo array. When the function is called with a value n, it first checks if the answer is already in memo. If yes, it returns that answer immediately. If not, it computes the answer by calling itself recursively for smaller values, stores the result in memo, and returns it. This avoids repeated work and speeds up the program. For example, in Fibonacci, base cases for n=0 or 1 return immediately. For larger n, the function calls Fib(n-1) and Fib(n-2), sums them, stores in memo, and returns. The execution table shows how memo fills step by step, and recursive calls reduce thanks to memo hits. This technique changes exponential recursion into efficient linear time.

Practice

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

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 intermediate results

Solution

1. Step 1: Understand memoization concept

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

2. Step 2: Compare options

   Only To store results of subproblems to avoid repeated calculations correctly describes this purpose. Sorting, converting recursion to iteration, or deleting results are unrelated.

3. Final Answer:

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

4. Quick Check:

   Memoization = store subproblem results [OK]

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

Common Mistakes:

• Confusing memoization with sorting or iteration
• Thinking memoization reduces memory by deleting data
• Assuming memoization changes recursion to iteration

2. Which of the following is the correct way to declare a memoization dictionary for integer keys and values in C#?

easy

A. int[] memo = new int();

B. List<int> memo = new List<int>();

C. Dictionary memo = new Dictionary();

D. HashSet<int> memo = new HashSet<int>();

Solution

1. Step 1: Identify suitable data structure for memoization

   Memoization requires storing key-value pairs, so Dictionary is appropriate.

2. Step 2: Check other options

   List<int> and int[] store only values without keys. HashSet<int> stores unique values but no key-value pairs.

3. Final Answer:

   Dictionary memo = new Dictionary(); -> Option C

4. Quick Check:

   Memo dictionary = Dictionary [OK]

Hint: Memo needs key-value pairs, so use Dictionary [OK]

Common Mistakes:

• Using List or array which lack keys
• Using HashSet which stores only unique values
• Incorrect syntax for dictionary declaration

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

using System;
using System.Collections.Generic;

class Program {
  static Dictionary memo = new Dictionary();

  static int Fib(int n) {
    if (n <= 1) return n;
    if (memo.ContainsKey(n)) return memo[n];
    memo[n] = Fib(n - 1) + Fib(n - 2);
    return memo[n];
  }

  static void Main() {
    Console.WriteLine(Fib(5));
  }
}

medium

A. 8

B. 5

C. 3

D. 13

Solution

1. Step 1: Understand Fibonacci calculation with memoization

   Fib(5) = Fib(4) + Fib(3). 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 B

4. Quick Check:

   Fib(5) = 5 [OK]

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

Common Mistakes:

• Confusing index starting point (0 or 1)
• Forgetting memoization does not change result
• Calculating Fib(5) as 8 or 13 incorrectly

4. Identify the error in the following memoized Fibonacci function and select the correct fix:

static Dictionary memo = new Dictionary();

static int Fib(int n) {
  if (n <= 1) return n;
  if (memo.ContainsKey(n)) return memo[n];
  int result = Fib(n - 1) + Fib(n - 2);
  return result;
}

medium

A. Change if (n <= 1) return n; to if (n < 0) return 0;

B. Change Dictionary to List<int> for memo

C. Remove memo.ContainsKey check to simplify code

D. Add memo[n] = result; before returning result

Solution

1. Step 1: Check memoization usage

   The function calculates result but never stores it in memo, so memoization fails.

2. Step 2: Fix by storing result in memo

   Adding memo[n] = result; before return saves the computed value for reuse.

3. Final Answer:

   Add memo[n] = result; before returning result -> Option D

4. Quick Check:

   Store result in memo before return [OK]

Hint: Always save computed result in memo before returning [OK]

Common Mistakes:

• Forgetting to store result in memo dictionary
• Changing base case incorrectly
• Removing memo check causing repeated work

5. You want to find the number of ways to climb a staircase of n steps, taking 1 or 2 steps at a time, using top-down memoization in C#. Which of the following code snippets correctly implements this using memoization?

hard

A. static Dictionary memo = new Dictionary();\nstatic int Ways(int n) {\n if (n == 0) return 1;\n if (n < 0) return 0;\n if (memo.ContainsKey(n)) return memo[n];\n memo[n] = Ways(n - 1) + Ways(n - 2);\n return memo[n];\n}

B. static int Ways(int n) {\n if (n == 0) return 1;\n if (n < 0) return 0;\n return Ways(n - 1) + Ways(n - 2);\n}

C. static Dictionary memo = new Dictionary();\nstatic int Ways(int n) {\n if (n <= 1) return n;\n if (memo.ContainsKey(n)) return memo[n];\n memo[n] = Ways(n - 1) + Ways(n - 2);\n return memo[n];\n}

D. static Dictionary memo = new Dictionary();\nstatic int Ways(int n) {\n if (n == 1) return 1;\n if (memo.ContainsKey(n)) return memo[n];\n memo[n] = Ways(n - 1) + Ways(n - 2);\n return memo[n];\n}

Solution

1. Step 1: Analyze base cases for climbing stairs

   When n=0, there is 1 way (standing still). When n<0, no ways (0).

2. Step 2: Check memoization and recursion

   static Dictionary memo = new Dictionary();\nstatic int Ways(int n) {\n if (n == 0) return 1;\n if (n < 0) return 0;\n if (memo.ContainsKey(n)) return memo[n];\n memo[n] = Ways(n - 1) + Ways(n - 2);\n return memo[n];\n} correctly uses memo dictionary, checks base cases, and sums ways(n-1) and ways(n-2).

3. Step 3: Identify errors in other options

   static int Ways(int n) {\n if (n == 0) return 1;\n if (n < 0) return 0;\n return Ways(n - 1) + Ways(n - 2);\n} lacks memoization. static Dictionary memo = new Dictionary();\nstatic int Ways(int n) {\n if (n <= 1) return n;\n if (memo.ContainsKey(n)) return memo[n];\n memo[n] = Ways(n - 1) + Ways(n - 2);\n return memo[n];\n} has wrong base case (n<=1 return n). static Dictionary memo = new Dictionary();\nstatic int Ways(int n) {\n if (n == 1) return 1;\n if (memo.ContainsKey(n)) return memo[n];\n memo[n] = Ways(n - 1) + Ways(n - 2);\n return memo[n];\n} misses base case for n=0.

4. Final Answer:

   static Dictionary<int, int> memo = new Dictionary<int, int>();\nstatic int Ways(int n) {\n if (n == 0) return 1;\n if (n < 0) return 0;\n if (memo.ContainsKey(n)) return memo[n];\n memo[n] = Ways(n - 1) + Ways(n - 2);\n return memo[n];\n} -> Option A

5. Quick Check:

   Base cases + memo + recursion = static Dictionary memo = new Dictionary();\nstatic int Ways(int n) {\n if (n == 0) return 1;\n if (n < 0) return 0;\n if (memo.ContainsKey(n)) return memo[n];\n memo[n] = Ways(n - 1) + Ways(n - 2);\n return memo[n];\n} [OK]

Hint: Base case n=0 returns 1; always store results in memo [OK]

Common Mistakes:

• Wrong base cases causing incorrect counts
• Not using memo causing slow recursion
• Returning n instead of 1 for base cases