Memoization Top Down DP in DSA C# - Time & Space Complexity

Time Complexity: Memoization Top Down DP

O(n)

Understanding Time Complexity

We analyze how using memoization in top-down dynamic programming affects the time taken by a recursive solution.

We want to know how the number of repeated calculations changes when we remember past results.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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];
}

// memo array initialized with -1 for all indices

This code calculates the nth Fibonacci number using recursion with memoization to avoid repeated work.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive calls to Fib with different n values.
• How many times: Each unique n from 0 to n is computed once and stored in memo.

How Execution Grows With Input

Each Fibonacci number from 0 up to n is calculated once, so the work grows roughly in a straight line with n.

Input Size (n)	Approx. Operations
10	About 10 calls
100	About 100 calls
1000	About 1000 calls

Pattern observation: The number of operations grows directly with n, not exponentially as in plain recursion.

Final Time Complexity

Time Complexity: O(n)

This means the time taken grows linearly with the input size because each subproblem is solved once.

Common Mistake

[X] Wrong: "Memoization still causes exponential time because of recursion calls."

[OK] Correct: Memoization stores results so each unique call happens once, preventing repeated work and reducing time drastically.

Interview Connect

Understanding how memoization changes recursion time is a key skill that shows you can optimize solutions by avoiding repeated calculations.

Self-Check

"What if we removed memoization and only used plain recursion? How would the time complexity change?"

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