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 a technique called memoization to remember results for each step.

🎯 Goal: Build a program that uses memoization with top-down dynamic programming to find the number of ways to climb n steps.

📋 What You'll Learn

Create an integer array called memo to store results for each step

Write a recursive function countWays that takes an integer n and returns the number of ways to climb n steps

Use memoization inside countWays to avoid repeated calculations

Print the number of ways to climb 5 steps

💡 Why This Matters

🌍 Real World

Memoization helps optimize problems where the same calculations repeat, like counting ways to climb stairs or calculating Fibonacci numbers.

💼 Career

Understanding memoization and dynamic programming is essential for software engineers to write efficient algorithms and solve complex problems quickly.

1

Create the memo array

Create an integer array called memo of size 6 and initialize all elements to -1.

DSA C

# Create an integer array called memo of size 6 and initialize all elements to -1
// Your code here

Hint

Use int memo[6] = {-1, -1, -1, -1, -1, -1}; to create and initialize the array.

2

Write the recursive function with memoization

Write a recursive function called countWays that takes an integer n and returns the number of ways to climb n steps. Use the memo array to store and reuse results. If n is 0 or 1, return 1. If memo[n] is not -1, return memo[n]. Otherwise, calculate countWays(n-1) + countWays(n-2), store it in memo[n], and return it.

DSA C

#include 

int memo[6] = {-1, -1, -1, -1, -1, -1};

// Write the recursive function countWays with memoization
// Your code here

int main() {
    return 0;
}

Hint

Use the base cases for 0 and 1 steps, check memo before recursion, and store results in memo.

3

Call the function for 5 steps

In the main function, call countWays with 5 and store the result in an integer variable called result.

DSA C

#include 

int memo[6] = {-1, -1, -1, -1, -1, -1};

int countWays(int n) {
    if (n == 0 || n == 1) {
        return 1;
    }
    if (memo[n] != -1) {
        return memo[n];
    }
    memo[n] = countWays(n - 1) + countWays(n - 2);
    return memo[n];
}

int main() {
    // Call countWays with 5 and store in result
    // Your code here
    return 0;
}

Hint

Use int result = countWays(5); inside main.

4

Print the result

Add a printf statement in the main function to print the value of result.

DSA C

#include 

int memo[6] = {-1, -1, -1, -1, -1, -1};

int countWays(int n) {
    if (n == 0 || n == 1) {
        return 1;
    }
    if (memo[n] != -1) {
        return memo[n];
    }
    memo[n] = countWays(n - 1) + countWays(n - 2);
    return memo[n];
}

int main() {
    int result = countWays(5);
    // Print the result
    // Your code here
    return 0;
}

Hint

Use printf("%d\n", result); to print the number of ways.

Practice

1. What is the main purpose of memoization in top-down dynamic programming?

easy

A. To convert recursive code into iterative code

B. To sort the input data before processing

C. To store results of subproblems to avoid repeated calculations

D. To increase the number of recursive calls

Solution

1. Step 1: Understand memoization concept

   Memoization saves answers of smaller problems so they don't get solved again.

2. Step 2: Identify its role in top-down DP

   It stores subproblem results during recursion to speed up the process.

3. Final Answer:

   To store results of subproblems to avoid repeated calculations -> Option C

4. Quick Check:

   Memoization = Store subproblem results [OK]

Hint: Memoization means saving answers to reuse later [OK]

Common Mistakes:

• Confusing memoization with sorting
• Thinking memoization converts recursion to iteration
• Believing memoization increases recursive calls

2. Which of the following is the correct way to declare a memoization array for Fibonacci numbers in C?

easy

A. int memo[] = new int[100];

B. int memo[100] = {0};

C. int memo = new int[100];

D. int memo(100);

Solution

1. Step 1: Recall C array declaration syntax

   In C, arrays are declared with fixed size and optional initialization like int memo[100] = {0};

2. Step 2: Check each option

   int memo[100] = {0}; uses correct C syntax. Options A and C use Java/C++ style. int memo(100); is invalid in C.

3. Final Answer:

   int memo[100] = {0}; -> Option B

4. Quick Check:

   C array declaration = int memo[100] = {0}; [OK]

Hint: C arrays use fixed size with square brackets [OK]

Common Mistakes:

• Using Java or C++ style array declarations in C
• Forgetting to initialize memo array to zero
• Using parentheses instead of brackets for arrays

3. What will be the output of the following C code snippet using memoization for Fibonacci?

int memo[10] = {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() {
  printf("%d", fib(5));
  return 0;
}

medium

A. 0

B. 8

C. 3

D. 5

Solution

1. Step 1: Trace fib(5) calls and memo usage

   fib(5) calls fib(4) + fib(3), and so on. Memo stores results to avoid repeats.

2. Step 2: Calculate fib(5)

   fib(0)=0, fib(1)=1, fib(2)=1, fib(3)=2, fib(4)=3, fib(5)=5.

3. Final Answer:

   5 -> Option D

4. Quick Check:

   fib(5) = 5 [OK]

Hint: Remember Fibonacci sequence: 0,1,1,2,3,5... [OK]

Common Mistakes:

• Confusing fib(5) with fib(6)
• Ignoring memoization effect
• Assuming memo array starts with all ones

4. Identify the error in this memoized Fibonacci function in C:

int memo[10];
int fib(int n) {
  if (n <= 1) return n;
  if (memo[n] != -1) return memo[n];
  memo[n] = fib(n-1) + fib(n-2);
  return memo[n];
}

int main() {
  printf("%d", fib(5));
  return 0;
}

medium

A. memo array is not initialized to -1

B. fib function should return void

C. Base case should be n == 0 only

D. memo array size is too small

Solution

1. Step 1: Check memo array initialization

   Memo is checked for -1 but never initialized, so contains garbage values.

2. Step 2: Understand impact on memoization

   Without initialization, memo[n] != -1 may be true incorrectly, causing wrong returns.

3. Final Answer:

   memo array is not initialized to -1 -> Option A

4. Quick Check:

   Initialize memo to -1 before use [OK]

Hint: Always initialize memo array before use [OK]

Common Mistakes:

• Forgetting to initialize memo array
• Changing base case incorrectly
• Assuming default zero initialization in C

5. Given the following top-down memoized code to count ways to climb stairs (1 or 2 steps), what is the output of countWays(4)? Assume memo array is initialized with -1.

int memo[100];
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() {
  for(int i=0; i<100; i++) memo[i] = -1;
  printf("%d", countWays(4));
  return 0;
}

hard

A. 5

B. 7

C. 8

D. 4

Solution

1. Step 1: Understand problem and base cases

   Ways to climb 0 steps = 1, negative steps = 0, ways(n) = ways(n-1)+ways(n-2).

2. Step 2: Calculate countWays(4)

   countWays(1)=1, countWays(2)=2, countWays(3)=3, countWays(4)=5.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   Ways to climb 4 steps = 5 [OK]

Hint: Count ways follow Fibonacci pattern starting with 1,1 [OK]

Common Mistakes:

• Confusing base cases for counting ways
• Not initializing memo array
• Mixing up countWays with Fibonacci values