Tabulation Bottom Up DP in DSA Java

Mental Model

Start solving the smallest parts first and build up to the full problem using a table.

Analogy: Like filling a staircase from the bottom step to the top, each step depends on the ones below it.

Index: 0  1  2  3  4  5
Table: [0][ ][ ][ ][ ][ ]
          ↑

Dry Run Walkthrough

Input: Find the 5th Fibonacci number using bottom-up tabulation

Goal: Fill a table from the smallest Fibonacci numbers up to the 5th to find the answer

Step 1: Initialize table with base cases: fib[0] = 0, fib[1] = 1

fib: [0][1][ ][ ][ ][ ]

Why: Base cases are known and needed to build larger results

Step 2: Calculate fib[2] = fib[1] + fib[0] = 1 + 0 = 1

fib: [0][1][1][ ][ ][ ]

Why: Use previous two results to find next Fibonacci number

Step 3: Calculate fib[3] = fib[2] + fib[1] = 1 + 1 = 2

fib: [0][1][1][2][ ][ ]

Why: Continue building up using known smaller results

Step 4: Calculate fib[4] = fib[3] + fib[2] = 2 + 1 = 3

fib: [0][1][1][2][3][ ]

Why: Each step depends on the two before it

Step 5: Calculate fib[5] = fib[4] + fib[3] = 3 + 2 = 5

fib: [0][1][1][2][3][5]

Why: Final answer is built from all previous computations

Result:

fib: [0][1][1][2][3][5]
Answer: 5

Annotated Code

DSA Java

public class BottomUpFibonacci {
    public static int fib(int n) {
        if (n <= 1) return n;
        int[] fib = new int[n + 1];
        fib[0] = 0; // base case
        fib[1] = 1; // base case
        for (int i = 2; i <= n; i++) {
            fib[i] = fib[i - 1] + fib[i - 2]; // build from smaller results
        }
        return fib[n];
    }

    public static void main(String[] args) {
        int n = 5;
        int result = fib(n);
        System.out.println("fib: " + java.util.Arrays.toString(java.util.Arrays.copyOfRange(fibArray(n), 0, n+1)));
        System.out.println("Answer: " + result);
    }

    private static int[] fibArray(int n) {
        int[] fib = new int[n + 1];
        fib[0] = 0;
        if (n >= 1) fib[1] = 1;
        for (int i = 2; i <= n; i++) {
            fib[i] = fib[i - 1] + fib[i - 2];
        }
        return fib;
    }
}

fib[0] = 0; // base case

initialize first known Fibonacci number

fib[1] = 1; // base case

initialize second known Fibonacci number

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

build each Fibonacci number from the two before it

return fib[n];

return the final computed Fibonacci number

Output

fib: [0, 1, 1, 2, 3, 5]

Answer: 5

Complexity Analysis

Time: O(n) because we fill the table once from 0 to n

Space: O(n) because we store all Fibonacci numbers up to n in the table

vs Alternative: Compared to naive recursion which is exponential, tabulation is much faster and avoids repeated work

Edge Cases

n = 0

Returns 0 immediately as base case

DSA Java

if (n <= 1) return n;

n = 1

Returns 1 immediately as base case

DSA Java

if (n <= 1) return n;

When to Use This Pattern

When you see a problem that can be broken into smaller overlapping subproblems and you want to avoid repeated work, use bottom-up tabulation to build solutions from the smallest cases up.

Common Mistakes

Mistake: Starting the loop from 0 or 1 instead of 2
Fix: Start from 2 because 0 and 1 are base cases already set

Mistake: Not initializing base cases before the loop
Fix: Always set fib[0] and fib[1] before building up

Summary

Computes results by filling a table from smallest subproblems up to the target.

Use when a problem has overlapping subproblems and optimal substructure.

The key is to solve and store small parts first, then use them to solve bigger parts.

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