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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Bottom-Up DP for Fibonacci

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

DSA Java

public class FibDP {
    public static void main(String[] args) {
        int n = 6;
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        System.out.println(dp[n]);
    }
}

A 8

B 13

C 5

D 21

💡 Hint

Remember Fibonacci sequence starts with 0, 1 and each next number is sum of previous two.

The Fibonacci sequence starting with 0,1 is: 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 Java code that calculates the number of ways to make change for amount 5 using coins {1,2} with bottom-up DP?

DSA Java

public class CoinChange {
    public static void main(String[] args) {
        int amount = 5;
        int[] coins = {1, 2};
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] += dp[i - coin];
            }
        }
        System.out.println(dp[amount]);
    }
}

A 4

B 3

C 5

D 6

💡 Hint

Count all combinations of coins that sum to 5.

Ways to make 5 with {1,2} are: 1+1+1+1+1, 1+1+1+2, 1+2+2 (order doesn't matter), total 3 ways.

🔧 Debug

advanced

Identify the error in bottom-up DP for Longest Increasing Subsequence length

What error will this Java code produce when run? It tries to find the length of the longest increasing subsequence using bottom-up DP.

DSA Java

public class LIS {
    public static void main(String[] args) {
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        int n = nums.length;
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
        }
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        int max = 0;
        for (int length : dp) {
            max = Math.max(max, length);
        }
        System.out.println(max);
    }
}

A ArrayIndexOutOfBoundsException

B 0

C NullPointerException

D 4

💡 Hint

Check if the code initializes dp correctly and updates max length properly.

The code correctly computes the length of the longest increasing subsequence which is 4 for the input array.

❓ Predict Output

advanced

Output of Bottom-Up DP for 0/1 Knapsack Maximum Value

What is the output of this Java code that uses bottom-up DP to find the maximum value for 0/1 knapsack with capacity 5 and items with weights {1,2,3} and values {6,10,12}?

DSA Java

public class Knapsack {
    public static void main(String[] args) {
        int[] weights = {1, 2, 3};
        int[] values = {6, 10, 12};
        int capacity = 5;
        int n = weights.length;
        int[][] dp = new int[n + 1][capacity + 1];
        for (int i = 1; i <= n; i++) {
            for (int w = 1; w <= capacity; w++) {
                if (weights[i - 1] <= w) {
                    dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
                } else {
                    dp[i][w] = dp[i - 1][w];
                }
            }
        }
        System.out.println(dp[n][capacity]);
    }
}

A 22

B 28

C 18

D 24

💡 Hint

Try to pick items to maximize value without exceeding capacity 5.

Best combination is items with weights 2 and 3 (values 10 + 12 = 22).

🧠 Conceptual

expert

Time Complexity of Bottom-Up DP for Subset Sum Problem

What is the time complexity of the bottom-up dynamic programming solution for the subset sum problem where n is the number of elements and sum is the target sum?

A O(n^2 * sum)

B O(n + sum)

C O(n * sum)

D O(2^n)

💡 Hint

Consider the DP table size and how many states are computed.

The DP table has n rows and sum+1 columns, so time complexity is O(n * sum).

Practice

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

easy

A. Solve the problem by recursion without storing results

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

C. Use random guesses to find the solution

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

Solution

1. Step 1: Understand Tabulation Approach

   Tabulation means filling a table starting from the smallest subproblems to bigger ones.

2. Step 2: Compare with other methods

   Unlike recursion, tabulation 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 D

4. Quick Check:

   Tabulation = Bottom Up DP [OK]

Hint: Think bottom-up: solve small parts first, then bigger [OK]

Common Mistakes:

• Confusing tabulation with recursion
• Thinking tabulation starts from the biggest problem
• Ignoring the use of a table to store results

2. Which of the following is the correct way to initialize a DP array for bottom-up Fibonacci in Java?

easy

A. int[] dp = new int[n+1]; dp[0] = 0; dp[1] = 1;

B. int[] dp = new int[n]; dp[1] = 0; dp[2] = 1;

C. int[] dp = new int[n+1]; dp[0] = 1; dp[1] = 1;

D. int[] dp = new int[n]; dp[0] = 0; dp[1] = 1;

Solution

1. Step 1: Check array size for Fibonacci

   We need size n+1 to store from 0 to n indices.

2. Step 2: Set base cases correctly

   Fibonacci starts with dp[0]=0 and dp[1]=1.

3. Final Answer:

   int[] dp = new int[n+1]; dp[0] = 0; dp[1] = 1; -> Option A

4. Quick Check:

   Base cases dp[0]=0, dp[1]=1 [OK]

Hint: Array size n+1 and dp[0]=0, dp[1]=1 for Fibonacci [OK]

Common Mistakes:

• Using wrong array size causing IndexOutOfBounds
• Swapping base case values
• Starting indices from 1 instead of 0

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

int n = 5;
int[] dp = new int[n+1];
dp[0] = 0; dp[1] = 1;
for (int i = 2; i <= n; i++) {
    dp[i] = dp[i-1] + dp[i-2];
}
System.out.println(dp[n]);

medium

A. 13

B. 5

C. 3

D. 8

Solution

1. Step 1: Trace DP array filling

   dp[2]=1, dp[3]=2, dp[4]=3, dp[5]=5 by adding previous two values.

2. Step 2: Output dp[5]

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

3. Final Answer:

   5 -> Option B

4. Quick Check:

   Fibonacci(5) = 5 [OK]

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

Common Mistakes:

• Confusing index with Fibonacci value
• Off-by-one errors in loop
• Printing wrong dp index

4. Identify the error in this bottom-up DP code for Fibonacci:

int n = 5;
int[] dp = new int[n];
dp[0] = 0; dp[1] = 1;
for (int i = 2; i <= n; i++) {
    dp[i] = dp[i-1] + dp[i-2];
}
System.out.println(dp[n]);

medium

A. Array size is too small, causing IndexOutOfBoundsException

B. Base cases dp[0] and dp[1] are incorrect

C. Loop condition should be i < n instead of i <= n

D. No error, code runs fine

Solution

1. Step 1: Check array size

   Array dp has size n=5, valid indices 0 to 4 only.

2. Step 2: Loop accesses dp[5]

   Loop runs i=2 to 5 inclusive, dp[5] access causes error.

3. Final Answer:

   Array size is too small, causing IndexOutOfBoundsException -> Option A

4. Quick Check:

   Array size must be n+1 for dp[n] access [OK]

Hint: Array size must cover all indices used in loop [OK]

Common Mistakes:

• Using array size n instead of n+1
• Ignoring loop boundary causing runtime error
• Assuming code runs without error

5. You want to find the number of ways to climb n stairs if you can take 1 or 2 steps at a time using bottom-up DP. Which code snippet correctly implements this?

hard

A. int[] dp = new int[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];

B. int[] dp = new int[n]; dp[0]=1; dp[1]=2; for(int i=2;i

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

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

Solution

1. Step 1: Initialize base cases for climbing stairs

   dp[0]=1 means 1 way to stand still; dp[1]=1 means 1 way to climb 1 step.

2. Step 2: Fill dp using sum of previous two steps

   For i≥2, dp[i] = dp[i-1] + dp[i-2] counts ways taking 1 or 2 steps.

3. Step 3: Check loop and return

   Loop runs i=2 to n inclusive; return dp[n] is correct.

4. Final Answer:

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

5. Quick Check:

   Climbing stairs DP uses dp[i]=dp[i-1]+dp[i-2] [OK]

Hint: Base dp[0]=1, dp[1]=1; sum previous two for dp[i] [OK]

Common Mistakes:

• Wrong base case values
• Multiplying instead of adding
• Incorrect loop start or end indices