Tabulation Bottom Up DP in DSA C

Mental Model

Build the answer step-by-step from the smallest parts up, storing results in a table to avoid repeating work.

Analogy: Like filling a staircase from the bottom step to the top, each step depends on the ones below it, so you solve small steps first and use them to reach the top.

Table: [0] [1] [2] [3] [4] ...
Values:  0   ?   ?   ?   ?  ...
↑ start filling from left to right

Dry Run Walkthrough

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

Goal: Calculate Fibonacci(5) by filling a table from the base cases up to 5

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

fib: [0]=0, [1]=1, [2]=?, [3]=?, [4]=?, [5]=?

Why: We need starting points to build the rest

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

fib: [0]=0, [1]=1, [2]=1, [3]=?, [4]=?, [5]=?

Why: Use known values to find next

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

fib: [0]=0, [1]=1, [2]=1, [3]=2, [4]=?, [5]=?

Why: Build on previous results

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

fib: [0]=0, [1]=1, [2]=1, [3]=2, [4]=3, [5]=?

Why: Continue building up

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

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

Why: Final answer reached

Result:

fib: 0 -> 1 -> 1 -> 2 -> 3 -> 5
Answer: 5

Annotated Code

DSA C

#include <stdio.h>

// Function to find nth Fibonacci number using bottom-up DP
int fibonacci(int n) {
    if (n == 0) return 0;
    int fib[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 subproblems
    }
    return fib[n];
}

int main() {
    int n = 5;
    int result = fibonacci(n);
    printf("Fibonacci(%d) = %d\n", n, result);
    return 0;
}

fib[0] = 0; // base case

Set first known Fibonacci number

fib[1] = 1; // base case

Set second known Fibonacci number

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

Fill table from bottom up using previous two values

return fib[n];

Return final computed Fibonacci number

Output

Fibonacci(5) = 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 an array

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 C

if (n == 0) return 0;

n = 1

Returns 1 immediately as base case

DSA C

fib[1] = 1; // base case

When to Use This Pattern

When you see a problem where the answer depends on smaller subproblems and you want to avoid repeated calculations, use bottom-up tabulation to build the solution step-by-step.

Common Mistakes

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

Mistake: Not allocating enough space for the array causes out-of-bounds errors
Fix: Declare array size as n+1 to include index n

Summary

Calculates answers by filling a table from smallest to largest subproblems.

Use when a problem can be broken into smaller overlapping subproblems.

Build solutions bottom-up to avoid repeated work and save time.

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