Tabulation Bottom Up DP in DSA C - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the DP table with zeros.

DSA C

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

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

An + 1

Bn

C1

Dn - 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using size n instead of n + 1 causes out-of-bound errors.

Forgetting to initialize the DP table.

The DP table size should be n + 1 to include the base case for zero.

2fill in blank

medium

Complete the code to fill the DP table bottom-up for the Fibonacci sequence.

DSA C

dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] [1] dp[i - 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.

Incorrect loop bounds.

Fibonacci numbers are calculated by adding the two previous numbers.

3fill in blank

hard

Fix the error in the code to correctly compute the minimum number of coins for amount n.

DSA C

int dp[n + 1];
dp[0] = 0;
for (int i = 1; i <= n; i++) {
    dp[i] = INT_MAX;
    for (int j = 0; j < m; j++) {
        if (coins[j] <= i) {
            dp[i] = [1](dp[i], dp[i - coins[j]] + 1);
        }
    }
}

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

Amax

Bsum

Cabs

Dmin

Attempts:

3 left

💡 Hint

Common Mistakes

Using max instead of min causes incorrect results.

Not updating dp[i] properly.

We want the minimum number of coins, so use the min function.

4fill in blank

hard

Fill both blanks to complete the code for counting ways to make change using bottom-up DP.

DSA C

int dp[n + 1] = {0};
dp[0] = 1;
for (int i = 0; i < m; i++) {
    for (int j = coins[i]; j <= n; j++) {
        dp[j] = dp[j] [1] dp[j [2] coins[i]];
    }
}

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

A+

B-

C[

D]

Attempts:

3 left

💡 Hint

Common Mistakes

Using subtraction instead of addition.

Incorrect operator in the index.

We add ways to make j without coin i and ways to make j - coins[i].

5fill in blank

hard

Fill the blanks to complete the code for longest common subsequence (LCS) using bottom-up DP.

DSA C

for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
        if (X[i - 1] == Y[j - 1]) {
            dp[i][j] = dp[i - 1][j - 1] [1] 1;
        } else {
            dp[i][j] = [2](dp[i - 1][j], dp[i][j - 1]);
        }
    }
}

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

A+

Bmax

C-

Dmin

Attempts:

3 left

💡 Hint

Common Mistakes

Using min instead of max for the else case.

Forgetting to add 1 when characters match.

When characters match, add 1 to dp[i-1][j-1]. Otherwise, take max of dp[i-1][j] and dp[i][j-1].