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.