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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Bottom-Up DP for Fibonacci

What is the output of the following C++ code that uses bottom-up dynamic programming to compute Fibonacci numbers?

DSA C++

int fib(int n) {
    int dp[n+1];
    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);
    std::cout << result << std::endl;
    return 0;
}

A 13

B 5

C 21

D 8

💡 Hint

Trace the Fibonacci sequence starting from 0,1 up to the 6th number.

The Fibonacci sequence starts as 0,1,1,2,3,5,8,... The 6th Fibonacci number (0-based) is 8.

❓ Predict Output

intermediate

Output of Bottom-Up DP for Coin Change Ways

What is the output of this C++ code that calculates the number of ways to make change for amount 5 using coins {1,2} with bottom-up DP?

DSA C++

int countWays(int coins[], int n, int amount) {
    int dp[amount+1] = {0};
    dp[0] = 1;
    for(int i = 0; i < n; i++) {
        for(int j = coins[i]; j <= amount; j++) {
            dp[j] += dp[j - coins[i]];
        }
    }
    return dp[amount];
}

int main() {
    int coins[] = {1, 2};
    int result = countWays(coins, 2, 5);
    std::cout << result << std::endl;
    return 0;
}

A 5

B 3

C 4

D 6

💡 Hint

Count all combinations of 1s and 2s that sum to 5.

Ways to make 5: (1+1+1+1+1), (1+1+1+2), (1+2+2). Order doesn't matter, so total 3 combinations.

🧠 Conceptual

advanced

Understanding DP Table Initialization

In bottom-up dynamic programming, why is it important to initialize the base cases in the DP table before filling the rest?

A Because initialization reduces the time complexity from exponential to linear.

B Because uninitialized values cause the program to crash immediately.

C Because base cases provide starting values needed to build solutions for larger subproblems.

D Because base cases are the only values used in the final answer.

💡 Hint

Think about how smaller problems help solve bigger problems.

Base cases give known answers for smallest subproblems, allowing the DP to build up solutions step-by-step.

🔧 Debug

advanced

Identify the Bug in Bottom-Up DP Code

What error will this C++ bottom-up DP code produce when run?

DSA C++

int fib(int n) {
    int dp[n];
    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() {
    std::cout << fib(5) << std::endl;
    return 0;
}

A Runtime error: accessing out-of-bounds array index

B Compilation error: missing return statement

C Output: 5

D Output: 8

💡 Hint

Check array size and loop limits carefully.

Array dp has size n but code accesses dp[n], which is out of bounds causing runtime error.

🚀 Application

expert

Minimum Steps to One Using Bottom-Up DP

Given the code below, what is the value of dp[10] after execution? dp[i] stores the minimum steps to reduce i to 1 by either subtracting 1, dividing by 2 if divisible, or dividing by 3 if divisible.

DSA C++

int minSteps(int n) {
    int dp[n+1];
    dp[1] = 0;
    for(int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + 1;
        if(i % 2 == 0) dp[i] = std::min(dp[i], dp[i/2] + 1);
        if(i % 3 == 0) dp[i] = std::min(dp[i], dp[i/3] + 1);
    }
    return dp[n];
}

int main() {
    std::cout << minSteps(10) << std::endl;
    return 0;
}

A 3

B 4

C 5

D 6

💡 Hint

Trace dp values from 1 to 10 carefully considering all operations.

Minimum steps for 10: 10->9 (subtract 1), 9->3 (divide by 3), 3->1 (divide by 3), total 3 steps.

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 largest problem and break it down

Solution

1. Step 1: Understand bottom-up approach

   Tabulation means filling a table starting from the smallest subproblems, so we solve all smaller parts first.

2. Step 2: Compare with other methods

   Unlike recursion without memory, bottom-up avoids repeated work by storing results in a table.

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 bottom-up with recursion without memoization
• Thinking it starts from the largest problem
• Ignoring the use of a table to store results

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[]; dp[1] = 1;

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

C. int dp[100]; dp[0] = 1;

D. int dp[100] = {1}; dp[2] = 1;

Solution

1. Step 1: Check array initialization

   int dp[100] = {0}; dp[1] = 1; initializes dp with zeros and sets dp[1] = 1, which is correct for Fibonacci base cases.

2. Step 2: Identify errors in other options

   int dp[]; dp[1] = 1; has no size for dp array, invalid in C++. int dp[100]; dp[0] = 1; sets dp[0] = 1 which is incorrect base case. int dp[100] = {1}; dp[2] = 1; initializes dp with 1 at dp[0], which is wrong.

3. Final Answer:

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

4. Quick Check:

   Correct base initialization = int dp[100] = {0}; dp[1] = 1; [OK]

Hint: Initialize dp array with zeros and set base cases explicitly [OK]

Common Mistakes:

• Not specifying array size
• Wrong base case initialization
• Assuming default values without initialization

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

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

int main() {
  std::cout << fib(5);
  return 0;
}

medium

A. 5

B. 8

C. 3

D. 13

Solution

1. Step 1: Trace dp array filling

   dp[0]=0, dp[1]=1; then dp[2]=1, dp[3]=2, dp[4]=3, dp[5]=5 by adding previous two.

2. Step 2: Return dp[5]

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

3. Final Answer:

   5 -> Option A

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 indexing
• Confusing dp[0] and dp[1] values
• Returning wrong dp index

4. Identify the error in this bottom-up DP code for computing factorial of n:

int factorial(int n) {
  int dp[100];
  dp[0] = 1;
  for (int i = 1; i <= n; i++) {
    dp[i] = dp[i-1] * i;
  }
  return dp[n];
}

medium

A. dp array not initialized to zero

B. Loop should start from i = 0

C. dp array size might be too small for large n

D. No error, code is correct

Solution

1. Step 1: Check dp array size

   dp array size is fixed at 100, so if n > 99, dp[i] access is out of bounds causing error.

2. Step 2: Analyze other parts

   Initialization and loop logic are correct; loop starts at 1 and dp[0] = 1 is base case.

3. Final Answer:

   dp array size might be too small for large n -> Option C

4. Quick Check:

   Array size must fit n [OK]

Hint: Ensure dp array size >= n to avoid overflow [OK]

Common Mistakes:

• Assuming dp size is always enough
• Starting loop at wrong index
• Ignoring base case initialization

5. Given the problem to find the minimum number of coins to make amount 11 using coins {1, 3, 5}, which bottom-up DP table entry dp[11] will hold after running this code?

int coins[] = {1, 3, 5};
int n = 11;
int dp[12];
dp[0] = 0;
for (int i = 1; i <= n; i++) {
  dp[i] = 1000; // large number
  for (int c : coins) {
    if (i - c >= 0) {
      dp[i] = std::min(dp[i], dp[i-c] + 1);
    }
  }
}
std::cout << dp[n];

hard

A. 6

B. 5

C. 4

D. 3

Solution

1. Step 1: Understand DP logic for coin change

   dp[i] stores minimum coins for amount i. For 11, check coins 1,3,5 and pick minimum.

2. Step 2: Calculate dp values up to 11

   dp[0]=0; dp[1]=1; dp[2]=2; dp[3]=1; dp[4]=2; dp[5]=1; dp[6]=2; dp[7]=3; dp[8]=2; dp[9]=3; dp[10]=2; dp[11]=3 (e.g., 5+5+1 or 3+3+5)

3. Final Answer:

   3 -> Option D

4. Quick Check:

   Minimum coins for 11 = 3 [OK]

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

Common Mistakes:

• Not initializing dp[0] = 0
• Using max int instead of large number
• Forgetting to check i - coin >= 0