Memoization Top Down DP in DSA C#

Mental Model

Remember answers to small problems so you don't solve them again.

Analogy: Like writing down answers to homework questions so you don't redo the same work later.

Problem -> Break into smaller problems -> Solve smaller problems -> Store answers in a table (cache) -> Use stored answers to build bigger answers

Dry Run Walkthrough

Input: Calculate Fibonacci number for n=5 using memoization

Goal: Find the 5th Fibonacci number efficiently by storing results of smaller Fibonacci calls

Step 1: Call fib(5), no cached answer, so compute fib(4) and fib(3)

Cache: {}

Why: We start with the big problem and break it down

Step 2: Call fib(4), no cached answer, so compute fib(3) and fib(2)

Cache: {}

Why: Still breaking down until base cases

Step 3: Call fib(3), no cached answer, so compute fib(2) and fib(1)

Cache: {}

Why: Keep breaking down

Step 4: Call fib(2), no cached answer, so compute fib(1) and fib(0)

Cache: {}

Why: Reach base cases

Step 5: fib(1) and fib(0) are base cases, return 1 and 0 respectively

Cache: {}

Why: Base cases stop recursion

Step 6: Calculate fib(2) = fib(1) + fib(0) = 1 + 0 = 1, store in cache

Cache: {2:1}

Why: Store result to avoid recomputing

Step 7: Calculate fib(3) = fib(2) + fib(1) = 1 + 1 = 2, store in cache

Cache: {2:1, 3:2}

Why: Use cached fib(2) and base fib(1)

Step 8: Calculate fib(4) = fib(3) + fib(2) = 2 + 1 = 3, store in cache

Cache: {2:1, 3:2, 4:3}

Why: Use cached values

Step 9: Calculate fib(5) = fib(4) + fib(3) = 3 + 2 = 5, store in cache

Cache: {2:1, 3:2, 4:3, 5:5}

Why: Final answer built from cached smaller answers

Result:

Cache: {2:1, 3:2, 4:3, 5:5}
Answer: 5

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class MemoizationTopDownDP
{
    static Dictionary<int, int> cache = new Dictionary<int, int>();

    static int Fib(int n)
    {
        if (n <= 1) return n; // base case

        if (cache.ContainsKey(n))
            return cache[n]; // return cached answer

        int result = Fib(n - 1) + Fib(n - 2); // recursive calls
        cache[n] = result; // store in cache
        return result;
    }

    static void Main()
    {
        int n = 5;
        int answer = Fib(n);
        Console.WriteLine($"Fib({n}) = {answer}");
    }
}

if (n <= 1) return n; // base case

stop recursion at smallest problems

if (cache.ContainsKey(n)) return cache[n]; // return cached answer

reuse stored answer to avoid recomputation

int result = Fib(n - 1) + Fib(n - 2); // recursive calls

break problem into smaller subproblems

cache[n] = result; // store in cache

save answer for future calls

Output

Fib(5) = 5

Complexity Analysis

Time: O(n) because each number from 0 to n is computed once and then reused

Space: O(n) for the cache storing results for each subproblem

vs Alternative: Compared to naive recursion with O(2^n) time, memoization reduces repeated work to linear time

Edge Cases

n = 0 (smallest input)

Returns 0 immediately as base case

DSA C#

if (n <= 1) return n; // base case

n = 1 (smallest input)

Returns 1 immediately as base case

DSA C#

if (n <= 1) return n; // base case

Repeated calls with same n

Uses cached result, no recomputation

DSA C#

if (cache.ContainsKey(n)) return cache[n]; // return cached answer

When to Use This Pattern

When a problem asks for a value defined by smaller subproblems and has overlapping calls, use memoization top down DP to save repeated work.

Common Mistakes

Mistake: Not storing the computed result in the cache after recursion
Fix: Add cache[n] = result after computing to save the answer

Mistake: Not checking cache before recursive calls
Fix: Check if cache contains n before recursion to reuse answers

Summary

It solves problems by remembering answers to smaller parts to avoid repeating work.

Use it when a problem can be broken into overlapping smaller problems.

The key is to store and reuse answers instead of recalculating them.

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