Memoization Top Down DP in DSA C++

Mental Model

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

Analogy: Like writing down answers to tricky homework questions so you can check them later instead of redoing the whole problem.

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

Dry Run Walkthrough

Input: Calculate Fibonacci number for n=5 using memoization

Goal: Find Fibonacci(5) efficiently by storing intermediate results

Step 1: Call fib(5), check memo, not found, so compute fib(4) and fib(3)

memo: [] (empty), call stack: fib(5) -> fib(4) -> fib(3)

Why: We start from the top problem and break it down

Step 2: Call fib(4), check memo, not found, compute fib(3) and fib(2)

memo: [] (empty), call stack: fib(5) -> fib(4) -> fib(3) -> fib(2)

Why: Keep breaking down until base cases

Step 3: Call fib(3), check memo, not found, compute fib(2) and fib(1)

memo: [] (empty), call stack: fib(5) -> fib(4) -> fib(3) -> fib(2) -> fib(1)

Why: Continue breaking down

Step 4: fib(2): fib(1) base returns 1, fib(0) base returns 0, fib(2)=1+0=1, store memo[2] = 1

memo: [_, _, 1, _, _, _], call stack unwinding

Why: fib(2) computed from base cases, store result

Step 5: fib(1) base case returns 1 (no store)

memo: [_, _, 1, _, _, _], call stack unwinding

Why: Base case reached, return result without storing

Step 6: fib(3) = fib(2) + fib(1) = 1 + 1 = 2, store memo[3] = 2

memo: [_, _, 1, 2, _, _]

Why: Combine stored results to get fib(3)

Step 7: fib(2) called again, found in memo as 1, no recomputation

memo: [_, _, 1, 2, _, _]

Why: Reuse stored result to save time

Step 8: fib(4) = fib(3) + fib(2) = 2 + 1 = 3, store memo[4] = 3

memo: [_, _, 1, 2, 3, _]

Why: Combine stored results to get fib(4)

Step 9: fib(3) called again, found in memo as 2, no recomputation

memo: [_, _, 1, 2, 3, _]

Why: Reuse stored result

Step 10: fib(5) = fib(4) + fib(3) = 3 + 2 = 5, store memo[5] = 5

memo: [_, _, 1, 2, 3, 5]

Why: Final answer computed using stored results

Result:

memo: [_, _, 1, 2, 3, 5]
Fibonacci(5) = 5

Annotated Code

DSA C++

#include <iostream>
#include <vector>

using namespace std;

int fib(int n, vector<int>& memo) {
    if (n <= 1) return n; // base case
    if (memo[n] != -1) return memo[n]; // return stored answer
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo); // store computed answer
    return memo[n];
}

int main() {
    int n = 5;
    vector<int> memo(n + 1, -1); // initialize memo with -1
    int result = fib(n, memo);
    cout << "Fibonacci(" << n << ") = " << result << endl;
    return 0;
}

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

return base Fibonacci values for 0 and 1

if (memo[n] != -1) return memo[n]; // return stored answer

reuse previously computed result to avoid recomputation

memo[n] = fib(n - 1, memo) + fib(n - 2, memo); // store computed answer

compute fib(n) by summing smaller subproblems and store result

Output

Fibonacci(5) = 5

Complexity Analysis

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

Space: O(n) for the memo array 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

Returns 0 immediately as base case

DSA C++

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

n = 1

Returns 1 immediately as base case

DSA C++

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

Repeated calls for same n

Returns stored result from memo without recomputation

DSA C++

if (memo[n] != -1) return memo[n]; // return stored answer

When to Use This Pattern

When a problem can be broken into overlapping smaller problems and you see repeated calls with same inputs, use memoization top down DP to save time by storing results.

Common Mistakes

Mistake: Not checking memo before recursive calls causing repeated work
Fix: Add a check to return memo[n] if already computed before recursion

Mistake: Not initializing memo array properly leading to wrong results
Fix: Initialize memo array with a sentinel value like -1 to detect uncomputed states

Summary

Stores answers to smaller problems to avoid repeated work in recursion.

Use when a problem has overlapping subproblems and recursion repeats work.

The key is to check and store results in a memo table before recursive calls.

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