Memoization Top Down DP in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Fibonacci with Memoization

What is the output of the following C# code that computes Fibonacci numbers using memoization?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static Dictionary<int, int> memo = new Dictionary<int, int>();

    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);
        memo[n] = result;
        return result;
    }

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

A 5

B 8

C 13

D 3

💡 Hint

Remember Fibonacci sequence starts with 0, 1, 1, 2, 3, 5...

Fib(5) = Fib(4) + Fib(3) = 3 + 2 = 5. The memo dictionary stores intermediate results to avoid repeated calculations.

❓ Predict Output

intermediate

Memoized Climbing Stairs Output

What is the output of this C# code that uses memoization to count ways to climb stairs?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static Dictionary<int, int> memo = new Dictionary<int, int>();

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

    static void Main() {
        Console.WriteLine(ClimbStairs(4));
    }
}

A 8

B 7

C 4

D 5

💡 Hint

Number of ways to climb 4 stairs with 1 or 2 steps at a time.

ClimbStairs(4) = ClimbStairs(3) + ClimbStairs(2) = 3 + 2 = 5 ways.

🔧 Debug

advanced

Identify the error in memoized factorial code

What error does this C# code produce when run?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static Dictionary<int, int> memo = new Dictionary<int, int>();

    static int Factorial(int n) {
        if (n == 0) return 1;
        if (memo.ContainsKey(n)) return memo[n];
        int result = n * Factorial(n - 1);
        memo[n] = result;
        return result;
    }

    static void Main() {
        Console.WriteLine(Factorial(-1));
    }
}

A StackOverflowException

B KeyNotFoundException

C ArgumentOutOfRangeException

D No error, prints 1

💡 Hint

Check the base case and input value.

Calling Factorial(-1) causes infinite recursion because base case only handles n == 0, leading to stack overflow.

🧠 Conceptual

advanced

Memoization Cache Behavior

In a top-down memoized Fibonacci function, what happens when Fib(6) is called after Fib(5) has been computed and cached?

A Fib(6) computes Fib(5) and Fib(4) again from scratch

B Fib(6) uses cached Fib(5) and computes Fib(4) recursively

C Fib(6) uses cached Fib(5) and Fib(4) without recomputation

D Fib(6) recomputes Fib(5) but uses cached Fib(4)

💡 Hint

Memoization stores all computed results for reuse.

After Fib(5) is computed, both Fib(5) and Fib(4) are cached. Fib(6) uses both cached values without recomputation.

🚀 Application

expert

Longest Increasing Subsequence Length with Memoization

Given the following C# code using memoization to find the length of the longest increasing subsequence (LIS), what is the output when input array is [10, 9, 2, 5, 3, 7, 101, 18]?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
    static Dictionary<int, int> memo = new Dictionary<int, int>();

    static int LIS(int currentIndex) {
        if (memo.ContainsKey(currentIndex)) return memo[currentIndex];
        int maxLength = 1;
        for (int next = currentIndex + 1; next < nums.Length; next++) {
            if (nums[next] > nums[currentIndex]) {
                int length = 1 + LIS(next);
                if (length > maxLength) maxLength = length;
            }
        }
        memo[currentIndex] = maxLength;
        return maxLength;
    }

    static void Main() {
        int maxLIS = 0;
        for (int i = 0; i < nums.Length; i++) {
            int length = LIS(i);
            if (length > maxLIS) maxLIS = length;
        }
        Console.WriteLine(maxLIS);
    }
}

A 7

B 4

C 6

D 5

💡 Hint

Longest increasing subsequence length for this array is 4.

The longest increasing subsequence is [2, 3, 7, 101] or [2, 5, 7, 101], length 4. The code computes the maximum length correctly using memoization.

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