Tabulation Bottom Up DP in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Bottom-Up DP Fibonacci Calculation

What is the output of the following C code that uses bottom-up dynamic programming to calculate the 6th Fibonacci number?

DSA C

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

int main() {
    int result = fib(6);
    printf("%d\n", result);
    return 0;
}

A 8

B 21

C 5

D 13

💡 Hint

Remember the Fibonacci sequence starts with 0, 1, 1, 2, 3, 5, 8...

The bottom-up DP fills dp array from 0 to 6. dp[6] = dp[5] + dp[4] = 5 + 3 = 8.

🧠 Conceptual

intermediate

Understanding Tabulation Table Size

In bottom-up dynamic programming for the coin change problem, if you have 5 coin types and want to make amount 10, what is the size of the DP table you typically create?

A A 2D table with 5 rows and 10 columns

B A 1D table with 5 elements

C A 2D table with 6 rows and 11 columns

D A 1D table with 11 elements

💡 Hint

Think about including zero coins and zero amount as base cases.

We create a table with rows = number of coin types + 1 (for zero coins) and columns = amount + 1 (for zero amount). So 6x11.

🔧 Debug

advanced

Identify the Error in Bottom-Up DP for Longest Increasing Subsequence

What error will this bottom-up DP code for longest increasing subsequence cause?

DSA C

int lengthOfLIS(int* nums, int numsSize) {
    int dp[numsSize];
    for (int i = 0; i < numsSize; i++) dp[i] = 1;
    for (int i = 1; i < numsSize; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                if (dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                }
            }
        }
    }
    int max = 1;
    for (int i = 0; i < numsSize; i++) {
        if (dp[i] > max) max = dp[i];
    }
    return max;
}

A It returns the correct length of the longest increasing subsequence

B It returns the length of the last increasing subsequence found, not the longest

C It returns the length of the longest decreasing subsequence instead

D It causes a runtime error due to uninitialized dp array

💡 Hint

Look at how dp[i] is updated inside the nested loop.

The code overwrites dp[i] without checking if dp[j] + 1 is greater than current dp[i], so it does not keep the max length.

❓ Predict Output

advanced

Output of Bottom-Up DP for 0/1 Knapsack

What is the output of this C code that uses bottom-up DP to solve 0/1 knapsack problem with weights {1, 3, 4} and values {15, 20, 30} and capacity 4?

DSA C

int max(int a, int b) { return (a > b) ? a : b; }

int knapsack(int W, int wt[], int val[], int n) {
    int dp[n+1][W+1];
    for (int i = 0; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            if (i == 0 || w == 0) dp[i][w] = 0;
            else if (wt[i-1] <= w)
                dp[i][w] = max(val[i-1] + dp[i-1][w - wt[i-1]], dp[i-1][w]);
            else
                dp[i][w] = dp[i-1][w];
        }
    }
    return dp[n][W];
}

int main() {
    int val[] = {15, 20, 30};
    int wt[] = {1, 3, 4};
    int W = 4;
    int n = 3;
    int result = knapsack(W, wt, val, n);
    printf("%d\n", result);
    return 0;
}

A 35

B 50

C 30

D 20

💡 Hint

Try to pick items that maximize value without exceeding capacity 4.

The best combination is items with weights 1 and 3 (values 15 + 20 = 35). Item with weight 4 alone has value 30.

🧠 Conceptual

expert

Time Complexity of Bottom-Up DP for Matrix Chain Multiplication

What is the time complexity of the bottom-up dynamic programming solution for the matrix chain multiplication problem with n matrices?

A O(n!)

B O(n^2)

C O(2^n)

D O(n^3)

💡 Hint

Consider the three nested loops used to fill the DP table.

The bottom-up DP uses three nested loops over n, resulting in cubic time complexity O(n^3).

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