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.