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 <stdio.h>
#define MAX 10

int memo[MAX];

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

A 8

B 21

C 13

D 34

💡 Hint

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

fib(7) returns the 7th Fibonacci number (starting from 0), which is 13 if counting from 0, but since fib(0)=0, fib(7) = 13. However, the code counts fib(0)=0, fib(1)=1, so fib(7) = 13. The correct output is 13.

❓ Predict Output

intermediate

Memoized Factorial Computation Output

What is the output of this C code that uses memoization to compute factorials?

DSA C

#include <stdio.h>
#define MAX 6

int memo[MAX];

int fact(int n) {
    if (n <= 1) return 1;
    if (memo[n] != -1) return memo[n];
    memo[n] = n * fact(n-1);
    return memo[n];
}

int main() {
    for (int i = 0; i < MAX; i++) memo[i] = -1;
    printf("%d\n", fact(5));
    return 0;
}

A 720

B 120

C 24

D 60

💡 Hint

Recall factorial of 5 is 5*4*3*2*1.

fact(5) = 5*4*3*2*1 = 120. The memoization stores intermediate results but does not change the final output.

🔧 Debug

advanced

Identify the Bug in Memoized Climbing Stairs Code

What error does the following C code produce when run, and why?

DSA C

#include <stdio.h>
#define MAX 6

int memo[MAX];

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

int main() {
    for (int i = 0; i < MAX; i++) memo[i] = -1;
    printf("%d\n", climb(5));
    return 0;
}

A Segmentation fault due to accessing memo[5] out of bounds

B Prints 5 correctly

C Compilation error due to missing return type

D Infinite recursion causing stack overflow

💡 Hint

Check array size and index usage carefully.

The memo array has size 6 (indices 0 to 5). The function climb(5) calls climb(4) and climb(3), but climb(4) calls climb(3) and climb(2). climb(3) calls climb(2) and climb(1). climb(2) calls climb(1) and climb(0). climb(0) is valid, but climb(n) accesses memo[n]. For n=5, memo[5] is accessed which is valid now. However, if MAX was 5, memo[5] would be out of bounds causing segmentation fault. The original code had MAX=5 which caused out-of-bounds access. Increasing MAX to 6 fixes the issue.

🧠 Conceptual

advanced

Memoization vs Tabulation in DP

Which statement correctly describes the difference between memoization and tabulation in dynamic programming?

A Memoization uses recursion with caching to avoid repeated work; tabulation solves subproblems iteratively in a bottom-up manner.

B Memoization solves subproblems bottom-up and stores results in a table; tabulation uses recursion with caching.

C Memoization and tabulation are identical techniques with different names.

D Tabulation uses recursion and memoization uses iteration.

💡 Hint

Think about how recursion and iteration relate to these techniques.

Memoization is a top-down approach using recursion and caching results to avoid repeated calculations. Tabulation is a bottom-up approach solving smaller subproblems iteratively and building up the solution.

🚀 Application

expert

Memoized Edit Distance Computation Output

What is the output of the following C code that computes the edit distance between two strings using memoization?

DSA C

#include <stdio.h>
#include <string.h>
#define MAX 10

int memo[MAX][MAX];

int min(int a, int b, int c) {
    int m = a < b ? a : b;
    return m < c ? m : c;
}

int editDist(char *s1, char *s2, int m, int n) {
    if (m == 0) return n;
    if (n == 0) return m;
    if (memo[m][n] != -1) return memo[m][n];
    if (s1[m-1] == s2[n-1])
        memo[m][n] = editDist(s1, s2, m-1, n-1);
    else
        memo[m][n] = 1 + min(editDist(s1, s2, m, n-1), editDist(s1, s2, m-1, n), editDist(s1, s2, m-1, n-1));
    return memo[m][n];
}

int main() {
    char s1[] = "kitten";
    char s2[] = "sitting";
    for (int i = 0; i < MAX; i++)
        for (int j = 0; j < MAX; j++)
            memo[i][j] = -1;
    printf("%d\n", editDist(s1, s2, strlen(s1), strlen(s2)));
    return 0;
}

A 2

B 4

C 5

D 3

💡 Hint

Edit distance between 'kitten' and 'sitting' is a classic example.

The edit distance between 'kitten' and 'sitting' is 3 (replace 'k'->'s', replace 'e'->'i', insert 'g'). The memoized function correctly computes this value.

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