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