Tabulation Bottom Up DP in DSA C - Time & Space Complexity

Time Complexity: Tabulation Bottom Up DP

O(n)

Understanding Time Complexity

We want to understand how fast a bottom-up dynamic programming solution runs as the input size grows.

Specifically, how the number of steps changes when we fill the table from the smallest subproblems up.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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];
}
    

This code calculates the nth Fibonacci number using bottom-up tabulation.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop that fills the dp array from 2 to n.
• How many times: Exactly n-1 times (from 2 up to n).

How Execution Grows With Input

Each new input number adds one more step to fill the dp table.

Input Size (n)	Approx. Operations
10	About 9 steps
100	About 99 steps
1000	About 999 steps

Pattern observation: The number of steps grows roughly in a straight line as n increases.

Final Time Complexity

Time Complexity: O(n)

This means the time to compute grows directly in proportion to the input size.

Common Mistake

[X] Wrong: "Dynamic programming always takes exponential time because it solves many subproblems."

[OK] Correct: Bottom-up DP solves each subproblem once and stores the result, so it runs in linear time here, not exponential.

Interview Connect

Understanding how bottom-up DP reduces repeated work is a key skill that shows you can write efficient code for problems with overlapping subproblems.

Self-Check

"What if we changed the loop to compute dp[i] using three previous values instead of two? How would the time complexity change?"

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