Why Dynamic Programming and When Recursion Alone Fails in DSA C - Test Your Knowledge

Practice - 5 Tasks

1fill in blank

easy

Complete the code to calculate Fibonacci numbers using simple recursion.

DSA C

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

Drag options to blanks, or click blank then click option'

A*

B-

C+

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using subtraction or multiplication instead of addition.

Forgetting to return the sum.

The Fibonacci sequence is defined as fib(n) = fib(n-1) + fib(n-2). So we add the two previous results.

2fill in blank

medium

Complete the code to add memoization to the recursive Fibonacci function.

DSA C

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

Drag options to blanks, or click blank then click option'

A/

B+

C*

D-

Attempts:

3 left

💡 Hint

Common Mistakes

Not checking if memo[n] is already computed.

Using wrong operator instead of '+'.

Memoization stores results to avoid repeated calculations. The addition operator combines the two previous Fibonacci numbers.

3fill in blank

hard

Fix the error in the recursive factorial function to correctly compute factorial.

DSA C

int factorial(int n) {
    if (n == 0) return 1;
    return n [1] factorial(n-1);
}

Drag options to blanks, or click blank then click option'

A*

B-

C+

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using '+' or '-' instead of '*'.

Missing base case for n == 0.

Factorial is the product of all positive integers up to n, so we multiply n by factorial(n-1).

4fill in blank

hard

Fill both blanks to create a bottom-up dynamic programming solution for Fibonacci.

DSA C

int fibDP(int n) {
    int dp[n+1];
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i [1] 1] [2] dp[i-2];
    }
    return dp[n];
}

Drag options to blanks, or click blank then click option'

A-

B+

D*

Attempts:

3 left

💡 Hint

Common Mistakes

Using addition instead of subtraction for index.

Using multiplication instead of addition for dp values.

The loop calculates each Fibonacci number by adding the two previous numbers: dp[i-1] + dp[i-2].

5fill in blank

hard

Fill all three blanks to implement memoized Fibonacci with initialization.

DSA C

int fibMemoInit(int n) {
    int memo[n+1];
    for (int i = 0; i <= n; i++) {
        memo[i] = [1];
    }
    return fibHelper(n, memo);
}

int fibHelper(int n, int memo[]) {
    if (n <= 1) return n;
    if (memo[n] != [2]) return memo[n];
    memo[n] = fibHelper(n-1, memo) [3] fibHelper(n-2, memo);
    return memo[n];
}

Drag options to blanks, or click blank then click option'

A-1

B0

C+

D*

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing memo with 0 instead of -1.

Checking memo[n] != 0 instead of != -1.

Using multiplication instead of addition.

Initialize memo array with -1 to mark uncomputed values. Check if memo[n] != -1 to reuse. Add results of recursive calls.