Memoization Top Down DP in DSA C# - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is memoization in the context of dynamic programming?

Memoization is a technique where we store the results of expensive function calls and reuse them when the same inputs occur again, avoiding repeated calculations.

beginner

How does top-down dynamic programming differ from bottom-up?

Top-down DP solves the problem by breaking it down recursively and storing results (memoization), while bottom-up DP solves smaller subproblems first and builds up to the solution iteratively.

beginner

In C#, what data structure is commonly used to implement memoization for integer inputs?

A dictionary (Dictionary) is commonly used to store computed results for integer inputs in memoization.

intermediate

Why is memoization important in recursive algorithms like Fibonacci calculation?

Memoization prevents exponential time complexity by storing and reusing results of overlapping subproblems, reducing the time to linear or polynomial.

intermediate

What is a key step to ensure memoization works correctly in a top-down DP approach?

Before computing a subproblem, check if its result is already stored in the memo dictionary; if yes, return it immediately to avoid recomputation.

What does memoization primarily help to avoid in recursive algorithms?

A Using extra memory

B Writing iterative code

C Repeated calculations of the same subproblems

D Sorting data

Memoization stores results of subproblems to avoid recalculating them multiple times.

Which data structure is best suited for memoization in C# when keys are integers?

A Dictionary<int, int>

B List<int>

C Queue<int>

D Stack<int>

Dictionary allows fast lookup and storage of computed results by integer keys.

In top-down DP, when do you store the result of a subproblem?

A Never

B Before computing it

C Only if it is zero

D After computing it for the first time

You store the result after computing it to reuse it later.

Which of these problems is a classic example to demonstrate memoization?

A Calculating Fibonacci numbers

B Finding maximum in an array

C Sorting an array

D Printing a string

Fibonacci calculation has overlapping subproblems, making it ideal for memoization.

What is the main advantage of top-down DP with memoization over plain recursion?

A Uses less memory

B Runs faster by avoiding repeated work

C Is easier to write iterative loops

D Does not use recursion

Memoization speeds up recursion by caching results and avoiding repeated calculations.

Explain how memoization works in a top-down dynamic programming approach using a simple example like Fibonacci numbers.

Think about how you remember answers to smaller problems to avoid redoing work.

Describe the steps to implement memoization in C# for a recursive function.

Focus on how you use a dictionary to save and reuse results.

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