Tabulation Bottom Up DP in DSA C - Build from Scratch

Tabulation Bottom Up DP: Climbing Stairs Problem

📖 Scenario: Imagine you want to climb a staircase with a certain number of steps. You can take either 1 step or 2 steps at a time. You want to find out how many different ways you can reach the top.

🎯 Goal: Build a program using tabulation (bottom-up dynamic programming) to calculate the number of ways to climb a staircase with n steps.

📋 What You'll Learn

Create an integer variable n with the value 5 representing the number of steps.

Create an integer array dp of size n+1 to store the number of ways to reach each step.

Initialize base cases for dp[0] and dp[1].

Use a for loop with variable i from 2 to n to fill the dp array using the relation dp[i] = dp[i-1] + dp[i-2].

Print the value of dp[n] which is the total number of ways to reach the top.

💡 Why This Matters

🌍 Real World

This technique helps in solving problems where you build solutions step-by-step using previous results, like counting ways, shortest paths, or resource allocation.

💼 Career

Dynamic programming is a key skill in software engineering interviews and real-world tasks involving optimization and efficient problem solving.

1

Create the number of steps variable

Create an integer variable called n and set it to 5.

DSA C

# Your code here

Hint

Use int n = 5; to create the variable.

2

Create and initialize the dp array

Create an integer array called dp of size n + 1. Initialize dp[0] to 1 and dp[1] to 1.

DSA C

int n = 5;
// Create dp array of size n+1 and initialize dp[0] and dp[1]
# Your code here

Hint

Remember array size is n + 1. Initialize the first two elements to 1.

3

Fill the dp array using a for loop

Use a for loop with variable i from 2 to n inclusive. Inside the loop, set dp[i] = dp[i - 1] + dp[i - 2].

DSA C

int n = 5;
int dp[6];
dp[0] = 1;
dp[1] = 1;
// Fill dp array using for loop
# Your code here

Hint

Use a for loop from 2 to n and update dp[i] as sum of previous two dp values.

4

Print the total number of ways to climb

Print the value of dp[n] using printf.

DSA C

int n = 5;
int dp[6];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
}
// Print dp[n]
# Your code here

Hint

Use printf("%d\n", dp[n]); to print the result.

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