Climbing Stairs Problem in DSA C

Mental Model

You want to find how many ways you can reach the top of stairs by taking 1 or 2 steps at a time.

Analogy: Imagine climbing a staircase where you can take either one step or two steps at once. Counting all possible ways to reach the top is like counting all paths you can take by choosing 1-step or 2-step moves.

Start -> [Step 0]
          ↓
        Step 1
          ↓
        Step 2
          ↓
        Step 3
          ↓
        ...
          ↓
        Step n (top)

Dry Run Walkthrough

Input: stairs: 4 steps

Goal: Find how many distinct ways to reach step 4 by taking 1 or 2 steps at a time

Step 1: Initialize ways to reach step 0 and step 1 as 1 each

ways[0] = 1, ways[1] = 1

Why: Base cases: only 1 way to stand still or take first step

Step 2: Calculate ways to reach step 2 as ways[1] + ways[0]

ways[2] = 1 + 1 = 2

Why: You can get to step 2 from step 1 or step 0

Step 3: Calculate ways to reach step 3 as ways[2] + ways[1]

ways[3] = 2 + 1 = 3

Why: You can get to step 3 from step 2 or step 1

Step 4: Calculate ways to reach step 4 as ways[3] + ways[2]

ways[4] = 3 + 2 = 5

Why: You can get to step 4 from step 3 or step 2

Result:

ways array: [1, 1, 2, 3, 5]
Answer: 5 ways to climb 4 steps

Annotated Code

DSA C

#include <stdio.h>

// Function to calculate number of ways to climb n stairs
int climbStairs(int n) {
    if (n <= 1) return 1; // Base case: 1 way to climb 0 or 1 step

    int ways[n+1];
    ways[0] = 1; // 1 way to stand at step 0
    ways[1] = 1; // 1 way to reach step 1

    for (int i = 2; i <= n; i++) {
        ways[i] = ways[i-1] + ways[i-2]; // sum ways from previous two steps
    }

    return ways[n];
}

int main() {
    int stairs = 4;
    int result = climbStairs(stairs);
    printf("Number of ways to climb %d stairs: %d\n", stairs, result);
    return 0;
}

if (n <= 1) return 1; // Base case: 1 way to climb 0 or 1 step

Handle smallest stairs cases directly

ways[0] = 1; // 1 way to stand at step 0

Initialize ways to stand still

ways[1] = 1; // 1 way to reach step 1

Initialize ways to reach first step

for (int i = 2; i <= n; i++) {

Iterate through steps from 2 to n

ways[i] = ways[i-1] + ways[i-2]; // sum ways from previous two steps

Calculate ways to current step by adding ways to previous two steps

return ways[n];

Return total ways to reach top step

Output

Number of ways to climb 4 stairs: 5

Complexity Analysis

Time: O(n) because we calculate ways for each step once

Space: O(n) because we store ways for all steps up to n

vs Alternative: Compared to recursive approach without memoization which is exponential, this dynamic programming approach is efficient and fast

Edge Cases

n = 0 (no stairs)

Returns 1 because standing still counts as one way

DSA C

if (n <= 1) return 1;

n = 1 (one stair)

Returns 1 because only one step to climb

DSA C

if (n <= 1) return 1;

When to Use This Pattern

When you see a problem asking for number of ways to reach a point with fixed step sizes, use dynamic programming to sum ways from previous reachable points.

Common Mistakes

Mistake: Forgetting base cases and starting from step 2 without initializing ways[0] and ways[1]
Fix: Always initialize ways[0] and ways[1] to 1 before loop

Mistake: Using recursion without memoization causing exponential time
Fix: Use bottom-up dynamic programming with array to store intermediate results

Summary

Calculates how many distinct ways to climb n stairs taking 1 or 2 steps at a time.

Use when counting paths with limited step sizes or moves.

The number of ways to reach a step equals sum of ways to reach the two previous steps.