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 dynamic programming?

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

beginner

In memoization, what data structure is commonly used to store intermediate results?

An array or a hash map (dictionary) is commonly used to store intermediate results indexed by the subproblem parameters.

intermediate

Why is memoization useful in recursive algorithms?

Memoization prevents repeated work by saving results of subproblems, which reduces the time complexity from exponential to polynomial in many cases.

beginner

What is the base case role in a top-down DP memoized function?

The base case provides the simplest answer without recursion, stopping the recursion and allowing the function to build solutions for bigger problems.

What does memoization store to optimize recursive calls?

A Input parameters only

B Results of subproblems

C All function calls

D Random values

Memoization stores results of subproblems to avoid recalculating them.

Which of the following best describes top-down DP?

A Recursive with memoization

B Iterative without recursion

C Greedy approach

D Brute force search

Top-down DP uses recursion combined with memoization to solve problems.

What happens if you do not use memoization in a recursive Fibonacci function?

A It never finishes

B It runs faster

C It uses less memory

D It runs exponentially slower

Without memoization, recursive Fibonacci recalculates many subproblems, causing exponential time.

Which data structure is NOT typically used for memoization?

A Array

B Hash map

C Stack

D Dictionary

Stacks are used for function calls, not for storing memoized results.

What is the main benefit of using top-down DP with memoization?

A Avoids repeated calculations

B Uses more CPU cycles

C Increases code complexity

D Removes base cases

Memoization avoids repeated calculations, improving efficiency.

Explain how memoization works in a top-down dynamic programming approach.

Think about how you remember answers to avoid solving the same problem twice.

Describe the role of base cases and memo storage in a memoized recursive function.

Base cases are like stopping points; memo is like a memory bank.

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