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

Time Complexity: Memoization Top Down DP

O(n)

Understanding Time Complexity

We want to understand how using memoization in top-down dynamic programming affects the time it takes to solve problems.

Specifically, how does remembering past answers change the number of steps as input grows?

Scenario Under Consideration

Analyze the time complexity of the following memoized Fibonacci function.

int fib(int n, vector<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];
}
    

This code calculates the nth Fibonacci number using recursion and stores results to avoid repeated work.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive calls to fib with smaller n.
• How many times: Each unique n from 0 to n is computed once and then reused.

How Execution Grows With Input

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

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

Pattern observation: The work grows directly with n, not faster.

Final Time Complexity

Time Complexity: O(n)

This means the time to finish grows in a straight line as the input number n grows.

Common Mistake

[X] Wrong: "Memoized recursion still does all calls like plain recursion, so it's exponential time."

[OK] Correct: Memoization saves results so each unique call happens once, cutting down repeated work drastically.

Interview Connect

Understanding how memoization changes time complexity shows you can improve slow recursive solutions, a key skill in many coding challenges.

Self-Check

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

Practice

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

easy

A. To reduce the memory usage by deleting variables

B. To sort the input data before processing

C. To store results of subproblems to avoid repeated calculations

D. To convert recursive code into iterative code

Solution

1. Step 1: Understand memoization concept

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

2. Step 2: Identify its role in top-down DP

   In top-down DP, memoization avoids repeated work by caching answers.

3. Final Answer:

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

4. Quick Check:

   Memoization = store subproblem results [OK]

Hint: Memoization caches answers to speed up recursion [OK]

Common Mistakes:

• Confusing memoization with sorting
• Thinking memoization reduces memory by deleting variables
• Believing memoization converts recursion to iteration

2. Which of the following is the correct way to declare a memo array for Fibonacci numbers in C++?

easy

A. int memo[1000];

B. int memo[1000] = {0};

C. int memo[] = new int[1000];

D. int memo(1000, 0);

Solution

1. Step 1: Check array initialization

   int memo[1000] = {0}; declares an array of size 1000 and initializes all elements to 0.

2. Step 2: Compare other options

   int memo[1000]; declares but does not initialize; C is invalid syntax in C++; D is invalid syntax for array.

3. Final Answer:

   int memo[1000] = {0}; -> Option B

4. Quick Check:

   Correct array declaration with initialization = int memo[1000] = {0}; [OK]

Hint: Initialize memo array with zeros to mark unvisited [OK]

Common Mistakes:

• Not initializing memo array causing garbage values
• Using invalid syntax for array declaration
• Confusing vector initialization with array

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

int memo[100] = {0};
int fib(int n) {
  if (n <= 1) return n;
  if (memo[n] != 0) return memo[n];
  memo[n] = fib(n-1) + fib(n-2);
  return memo[n];
}
int main() {
  std::cout << fib(5);
  return 0;
}

medium

A. 5

B. 8

C. 3

D. 0

Solution

1. Step 1: Trace fib(5) calls

   fib(5) = fib(4) + fib(3), fib(4) = 3, fib(3) = 2, so fib(5) = 5.

2. Step 2: Confirm memoization usage

   Memo stores results to avoid repeated calls but does not change output.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   fib(5) = 5 [OK]

Hint: Remember fib(5) = 5 in Fibonacci sequence [OK]

Common Mistakes:

• Confusing fib(5) with fib(6)
• Ignoring base cases n <= 1
• Assuming memo array starts with all zeros means zero output

4. Identify the error in this memoized Fibonacci function:

int memo[100] = {0};
int fib(int n) {
  if (n == 0) return 0;
  if (n == 1) return 1;
  if (memo[n] != 0) return memo[n];
  memo[n] = fib(n-1) + fib(n-2);
  return memo[n];
}

medium

A. No error, code works correctly

B. Memo array initialization is incorrect

C. fib(2) returns wrong value due to memo check

D. Base case for n == 0 is missing

Solution

1. Step 1: Trace fib(2)

   fib(2) calls fib(1) and fib(0), returns 1 + 0 = 1 correctly, memo[2] = 1.

2. Step 2: Check memo condition

   Base cases are before memo check, so fib(0)=0 and fib(1)=1 always handled directly. For n>=2, fib(n) > 0.

3. Step 3: No error present

   Code produces correct results; using -1 init is better practice generally but not required here.

4. Final Answer:

   No error, code works correctly -> Option A

5. Quick Check:

   fib(2) = 1 correctly [OK]

Hint: Use a special value (e.g., -1) to mark unvisited memo entries [OK]

Common Mistakes:

• Assuming zero means unvisited memo entry
• Not handling base cases properly in memoization
• Ignoring that fib(0) = 0 causes memo check issues

5. Given the following top-down memoized code for counting ways to climb stairs (1 or 2 steps), what is the output of countWays(4)?

int memo[100] = {-1};
int countWays(int n) {
  if (n == 0) return 1;
  if (n < 0) return 0;
  if (memo[n] != -1) return memo[n];
  memo[n] = countWays(n-1) + countWays(n-2);
  return memo[n];
}
int main() {
  std::cout << countWays(4);
  return 0;
}

hard

A. 6

B. 7

C. 8

D. 5

Solution

1. Step 1: Understand problem and base cases

   countWays(0) = 1 means one way to stand still; countWays(n) sums ways from n-1 and n-2 steps.

2. Step 2: Calculate countWays(4)

   countWays(4) = countWays(3) + countWays(2) countWays(3) = countWays(2) + countWays(1) countWays(2) = countWays(1) + countWays(0) countWays(1) = countWays(0) + countWays(-1) = 1 + 0 = 1 countWays(0) = 1 So, countWays(2) = 1 + 1 = 2 countWays(3) = 2 + 1 = 3 countWays(4) = 3 + 2 = 5

3. Final Answer:

   5 -> Option D

4. Quick Check:

   Ways to climb 4 stairs = 5 [OK]

Hint: Count ways by summing previous two counts [OK]

Common Mistakes:

• Forgetting base case countWays(0) = 1
• Miscounting negative step returns
• Not initializing memo with -1 to mark unvisited