Climbing Stairs Problem in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Climbing Stairs Recursive Function

What is the output of the following C code when n = 4?

DSA C

#include <stdio.h>

int climbStairs(int n) {
    if (n <= 2) return n;
    return climbStairs(n - 1) + climbStairs(n - 2);
}

int main() {
    int result = climbStairs(4);
    printf("%d\n", result);
    return 0;
}

A 5

B 7

C 6

D 4

💡 Hint

Think about how many ways to climb 3 steps and 2 steps add up for 4 steps.

The function returns the number of ways to climb n stairs by summing ways to climb n-1 and n-2 stairs. For n=4, ways = climbStairs(3) + climbStairs(2) = 3 + 2 = 5.

❓ Predict Output

intermediate

Output of Climbing Stairs with Memoization

What is the output of this C code snippet when n = 5?

DSA C

#include <stdio.h>

int memo[100] = {0};

int climbStairs(int n) {
    if (n <= 2) return n;
    if (memo[n] != 0) return memo[n];
    memo[n] = climbStairs(n - 1) + climbStairs(n - 2);
    return memo[n];
}

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

A 10

B 7

C 5

D 8

💡 Hint

Memoization stores results to avoid repeated calculations.

The memoized function calculates climbStairs(5) = climbStairs(4) + climbStairs(3) = 5 + 3 = 8.

🔧 Debug

advanced

Identify the Logical Error in Climbing Stairs Iterative Code

What is the output of this code snippet and what is the logical error?

DSA C

#include <stdio.h>

int climbStairs(int n) {
    int a = 1, b = 1, c = 0;
    for (int i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return c;
}

int main() {
    int result = climbStairs(3);
    printf("%d\n", result);
    return 0;
}

A Output: 3; Error: Initial values cause off-by-one in counting ways

B Output: 5; Error: Loop runs too few times

C Output: 2; Error: Variables a and b are swapped incorrectly

D Output: 0; Error: Variable c is not initialized properly

💡 Hint

Check the base cases and loop start index carefully.

The code outputs 3 for n=3 which is correct. However, initial values a=1, b=1 cause the count to start from step 1 incorrectly, leading to confusion in interpretation.

🧠 Conceptual

advanced

Time Complexity of Climbing Stairs Recursive vs Dynamic Programming

Which option correctly describes the time complexity difference between the naive recursive and dynamic programming solutions for the climbing stairs problem?

A Both naive recursion and dynamic programming have quadratic O(n^2) complexity

B Naive recursion is linear O(n), dynamic programming is exponential O(2^n)

C Naive recursion is exponential O(2^n), dynamic programming is linear O(n)

D Naive recursion is logarithmic O(log n), dynamic programming is linear O(n)

💡 Hint

Think about how many times the recursive calls repeat work.

Naive recursion repeats many calls leading to exponential time. Dynamic programming stores results and computes each subproblem once, leading to linear time.

🚀 Application

expert

Number of Ways to Climb Stairs with Variable Steps

Given you can climb 1, 3, or 5 steps at a time, what is the number of ways to climb 6 steps? Choose the correct output of the following code.

DSA C

#include <stdio.h>

int climbVariableSteps(int n) {
    int dp[7] = {0};
    dp[0] = 1;
    for (int i = 1; i <= n; i++) {
        if (i - 1 >= 0) dp[i] += dp[i - 1];
        if (i - 3 >= 0) dp[i] += dp[i - 3];
        if (i - 5 >= 0) dp[i] += dp[i - 5];
    }
    return dp[n];
}

int main() {
    int result = climbVariableSteps(6);
    printf("%d\n", result);
    return 0;
}

A 12

B 8

C 15

D 10

💡 Hint

Count ways by adding ways from steps 1, 3, and 5 behind.

The dp array counts ways to reach each step by summing ways from i-1, i-3, and i-5. For n=6, dp[6] = dp[5] + dp[3] + dp[1] = 5 + 2 + 1 = 8.