Memoization Top Down DP in DSA C++ - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to declare the memo array for storing intermediate results.

DSA C++

int memo[[1]];

Drag options to blanks, or click blank then click option'

A1000

B0

Cn+1

Dn-1

Attempts:

3 left

💡 Hint

Common Mistakes

Using size 0 or n-1 causes out-of-bound errors.

Using a fixed size like 1000 wastes memory if n is small.

The memo array size should be n+1 to store results for all states from 0 to n.

2fill in blank

medium

Complete the code to check if the result is already computed in memo.

DSA C++

if (memo[n] != [1]) return memo[n];

Drag options to blanks, or click blank then click option'

An

B-1

C1

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Checking for 0 or 1 instead of -1.

Not initializing memo with -1 before.

We initialize memo with -1 to indicate uncomputed states. So we check if memo[n] != -1.

3fill in blank

hard

Fix the error in the recursive call to compute the result for n-1.

DSA C++

int result = [1](n - 1, memo) + n;

Drag options to blanks, or click blank then click option'

Asolve

BSolve

CsolveMemo

Dsolve_memo

Attempts:

3 left

💡 Hint

Common Mistakes

Using incorrect capitalization.

Using a different function name than defined.

The function name is 'solve' and should be called exactly as defined.

4fill in blank

hard

Fill both blanks to initialize memo and set base case value.

DSA C++

std::fill(memo, memo + [1], [2]);
memo[0] = 0;

Drag options to blanks, or click blank then click option'

An+1

B-1

C0

Dn

Attempts:

3 left

💡 Hint

Common Mistakes

Filling with 0 instead of -1.

Using n instead of n+1 for size.

We fill memo with -1 for all n+1 elements to mark uncomputed states. Base case memo[0] is set to 0.

5fill in blank

hard

Fill all three blanks to complete the memoization function.

DSA C++

int solve(int n, int memo[]) {
    if (n == 0) return 0;
    if (memo[n] != [1]) return memo[n];
    int result = solve(n [2] 1, memo) + n;
    memo[n] = [3];
    return memo[n];
}

Drag options to blanks, or click blank then click option'

A-1

B-

Cresult

D+

Attempts:

3 left

💡 Hint

Common Mistakes

Using + instead of - in recursive call.

Not storing result in memo[n].

Checking for 0 instead of -1.

Check if memo[n] != -1, then call solve(n - 1, memo) + n, store result in memo[n].

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