Memoization Top Down DP in DSA C++ - Build from Scratch

Memoization Top Down DP

📖 Scenario: You are helping a farmer count the number of ways to climb a staircase with n steps. The farmer can climb either 1 or 2 steps at a time. To avoid repeated work, you will use memoization to remember results for each step.

🎯 Goal: Build a memoized top-down dynamic programming solution in C++ to find the number of ways to climb n steps.

📋 What You'll Learn

Create an integer variable n with value 5

Create a vector memo of size n+1 initialized with -1

Write a recursive function countWays that takes step and memo and returns the number of ways to reach n from step

Use memoization inside countWays to avoid repeated calculations

Print the number of ways to climb n steps by calling countWays(0, memo)

💡 Why This Matters

🌍 Real World

Counting ways to climb stairs models many problems like counting paths, sequences, or combinations in real life.

💼 Career

Memoization and dynamic programming are key skills for software engineers solving optimization and combinatorial problems.

1

Create the number of steps variable

Create an integer variable called n and set it to 5.

DSA C++

# Your code here

Hint

Use int n = 5; to create the variable.

2

Create the memoization vector

Create a vector of integers called memo with size n + 1 and initialize all elements to -1.

DSA C++

int n = 5;
// Your code here

Hint

Use std::vector memo(n + 1, -1); to create the memo vector.

3

Write the memoized recursive function

Write a recursive function called countWays that takes an integer step and a reference to the vector memo. It should return the number of ways to reach step n from step. Use memoization to store and reuse results in memo. The base case is when step == n return 1, and when step > n return 0. For other cases, return the sum of countWays(step + 1, memo) and countWays(step + 2, memo).

DSA C++

int n = 5;
std::vector memo(n + 1, -1);

// Your code here

Hint

Remember to check if memo[step] is not -1 before computing recursively.

4

Print the number of ways to climb the stairs

Print the result of calling countWays(0, memo).

DSA C++

int n = 5;
std::vector memo(n + 1, -1);

int countWays(int step, std::vector& memo) {
    if (step == n) return 1;
    if (step > n) return 0;
    if (memo[step] != -1) return memo[step];
    memo[step] = countWays(step + 1, memo) + countWays(step + 2, memo);
    return memo[step];
}

// Your code here

Hint

Use std::cout << countWays(0, memo) << std::endl; inside main() to print the result.

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