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].

Practice

1. What is the main idea behind Tabulation Bottom Up DP in dynamic programming?

easy

A. Build a table from the smallest subproblems up to the main problem

B. Solve the problem by recursion without storing results

C. Use random guesses to find the solution

D. Start solving from the biggest problem and break it down

Solution

1. Step 1: Understand the DP approach

   Tabulation means filling a table starting from the smallest subproblems.

2. Step 2: Compare with other methods

   Unlike recursion without storage, tabulation avoids repeated work by building up solutions.

3. Final Answer:

   Build a table from the smallest subproblems up to the main problem -> Option A

4. Quick Check:

   Bottom Up DP = Build table from small to big [OK]

Hint: Think: solve small parts first, then bigger ones [OK]

Common Mistakes:

• Confusing tabulation with recursion without memoization
• Thinking tabulation starts from the biggest problem
• Assuming tabulation guesses solutions randomly

2. Which of the following is the correct way to declare a DP table for Fibonacci numbers using tabulation in C?

easy

A. int dp[] = {0};

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

C. int dp = 100;

D. int dp(100);

Solution

1. Step 1: Check C array declaration syntax

   In C, arrays are declared with size and type, e.g., int dp[100];

2. Step 2: Identify correct initialization

   int dp[100] = {0}; declares an int array of size 100 initialized to zero, suitable for DP table.

3. Final Answer:

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

4. Quick Check:

   C arrays need size and type [OK]

Hint: Use int dp[size] = {0} for zero-initialized arrays [OK]

Common Mistakes:

• Using parentheses instead of brackets for arrays
• Not specifying array size
• Assigning integer to array variable

3. What will be the output of the following C code using bottom-up DP to find Fibonacci number for n=5?

#include 
int main() {
    int n = 5;
    int dp[6] = {0};
    dp[0] = 0;
    dp[1] = 1;
    for(int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    printf("%d", dp[n]);
    return 0;
}

medium

A. 13

B. 8

C. 3

D. 5

Solution

1. Step 1: Trace DP table filling

   dp[0]=0, dp[1]=1; then dp[2]=1, dp[3]=2, dp[4]=3, dp[5]=5.

2. Step 2: Identify dp[n] value

   dp[5] = 5, so output is 5.

3. Final Answer:

   5 -> Option D

4. Quick Check:

   Fibonacci(5) = 5 [OK]

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

Common Mistakes:

• Off-by-one errors in loop range
• Confusing dp indices with Fibonacci numbers
• Printing dp[n-1] instead of dp[n]

4. Find the error in this bottom-up DP code snippet for Fibonacci numbers:

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

medium

A. Array dp is not initialized to zero

B. Return statement should be dp[n-1]

C. Loop starts at 1 instead of 2 causing invalid access

D. Function should return void

Solution

1. Step 1: Check loop start index

   Loop starts at i=1, but dp[i-2] for i=1 is dp[-1], invalid index.

2. Step 2: Correct loop start

   Loop should start at i=2 to avoid negative index access.

3. Final Answer:

   Loop starts at 1 instead of 2 causing invalid access -> Option C

4. Quick Check:

   Loop must start at 2 to access dp[i-2] safely [OK]

Hint: Start loop at 2 for Fibonacci tabulation [OK]

Common Mistakes:

• Starting loop at 1 causing negative index
• Ignoring array bounds in DP
• Returning wrong dp index

5. Given the problem to find the minimum number of coins to make amount 7 using coins {1, 3, 4} with bottom-up DP, what is the minimum number of coins needed? Use this approach:

int coins[] = {1, 3, 4};
int amount = 7;
int dp[8];
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
    dp[i] = INT_MAX;
    for (int j = 0; j < 3; j++) {
        if (coins[j] <= i && dp[i - coins[j]] != INT_MAX) {
            dp[i] = dp[i] < dp[i - coins[j]] + 1 ? dp[i] : dp[i - coins[j]] + 1;
        }
    }
}
printf("%d", dp[amount]);

hard

A. 2

B. 4

C. 3

D. 5

Solution

1. Step 1: Calculate dp values step-by-step

   dp[0]=0 For i=1: dp[1]=1 (coin 1) For i=2: dp[2]=2 (1+1) For i=3: dp[3]=1 (coin 3) For i=4: dp[4]=1 (coin 4) For i=5: dp[5]=2 (4+1) For i=6: dp[6]=2 (3+3) For i=7: dp[7]=2 (3+4)

2. Step 2: Identify minimum coins for amount 7

   Minimum coins needed for 7 is 2.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Minimum coins for 7 = 2 [OK]

Hint: Build dp from 0 to amount, pick min coins each step [OK]

Common Mistakes:

• Not updating dp[i] with minimum value
• Ignoring INT_MAX checks causing wrong results
• Confusing coin values and indices