Memoization Top Down DP in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Memoized Fibonacci Function

What is the output of the following C++ code that uses memoization to compute Fibonacci numbers?

DSA C++

#include <iostream>
#include <vector>
using namespace std;

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

int main() {
    int n = 6;
    vector<int> memo(n+1, -1);
    cout << fib(n, memo) << endl;
    return 0;
}

A 8

B 15

C 13

D 21

💡 Hint

Recall the Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13...

fib(0)=0, fib(1)=1, fib(2)=1, fib(3)=2, fib(4)=3, fib(5)=5, fib(6)=8. The code outputs 8.

🧠 Conceptual

intermediate

Memoization Purpose in Top Down DP

What is the main purpose of using memoization in a top-down dynamic programming approach?

A To convert recursion into iteration

B To store intermediate results to avoid repeated calculations

C To sort the input data before processing

D To reduce memory usage by deleting variables

💡 Hint

Think about how recursion can repeat the same work multiple times.

Memoization saves results of subproblems so that when the same subproblem occurs again, the stored result is used instead of recalculating.

🔧 Debug

advanced

Identify the Error in Memoized Climbing Stairs Code

What error will occur when running this C++ code for climbing stairs with memoization?

DSA C++

#include <iostream>
#include <vector>
using namespace std;

int climbStairs(int n, vector<int>& memo) {
    if (n <= 1) return 1;
    if (memo[n] != 0) return memo[n];
    memo[n] = climbStairs(n-1, memo) + climbStairs(n-2, memo);
    return memo[n];
}

int main() {
    int n = 5;
    vector<int> memo(n+1);
    cout << climbStairs(n, memo) << endl;
    return 0;
}

A Outputs 8

B Outputs 13

C Runtime error due to out-of-range access

D Outputs 0

💡 Hint

Check how memo vector is initialized and how base cases are handled.

The code initializes memo with zeros, so memo[n] != 0 check works. Base case returns 1 for n <= 1. climbStairs(5) returns 8.

❓ Predict Output

advanced

Output of Memoized Coin Change Ways

What is the output of this C++ code that uses memoization to count ways to make change?

DSA C++

#include <iostream>
#include <vector>
using namespace std;

int countWays(int amount, const vector<int>& coins, int index, vector<vector<int>>& memo) {
    if (amount == 0) return 1;
    if (amount < 0 || index == coins.size()) return 0;
    if (memo[amount][index] != -1) return memo[amount][index];
    int include = countWays(amount - coins[index], coins, index, memo);
    int exclude = countWays(amount, coins, index + 1, memo);
    memo[amount][index] = include + exclude;
    return memo[amount][index];
}

int main() {
    int amount = 5;
    vector<int> coins = {1, 2, 5};
    vector<vector<int>> memo(amount + 1, vector<int>(coins.size(), -1));
    cout << countWays(amount, coins, 0, memo) << endl;
    return 0;
}

A 6

B 5

C 3

D 4

💡 Hint

Count all combinations of coins that sum to 5.

The ways to make 5 are: {5}, {2,2,1}, {2,1,1,1}, {1,1,1,1,1} totaling 4 ways.

🧠 Conceptual

expert

Why Memoization Can Use More Memory Than Bottom-Up DP

Why can memoization in top-down dynamic programming sometimes use more memory than bottom-up DP?

A Because bottom-up DP always uses less memory by design

B Because memoization deletes stored results after use

C Because recursion call stack adds overhead and memo stores all subproblems lazily

D Because bottom-up DP does not store any intermediate results

💡 Hint

Consider recursion stack and when memo entries are created.

Memoization stores results as needed but recursion stack frames remain until calls return, increasing memory usage compared to iterative bottom-up DP.

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