Number of ways to climb a stair having n steps – LeetCode Solution [Easy]

You are climbing a staircase. It has n steps upto the top. Each time you can either climb 1 step or 2 steps. You’ve to find the number of ways to climb the stair.

Example 1:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

This problem could be solved by Dynamic programming.

Optimal substructure

Let S[i] be the number of ways to reach the ith step.

Base case
S[1] = 1, S[2] = 2
S[i] = S[i-1] + S[i-2], for i = 3 to n 

S[3] = S[2]  + S[1], ie.
S[3] = (number of ways to reach 2nd step + 
        number of ways to reach 1st step)


Now, let’s consider it for the nth step (S[n]):
(2 cases could happen) 
1. S[n-1] (no. of ways to reach n-1th step) + 1 step
2. S[n-2] (no. of ways to reach n-2th step) + 2 steps

Therefore, we could induce that, 
S[n] = S[n-1] + S[n-2]

Note: Here, we’re counting the number of ways to climb the stairs and not the number of steps taken.

Code Implementation

Bottom up approach

//
//  main.cpp
//  Climbing steps
//
//  Created by Himanshu on 19/09/21.
//

#include <iostream>
using namespace std;

int solve (int n) {
    int steps[n+1];
    
    if (n == 1) {
        return 1;
    } else if (n == 2) {
        return 2;
    }
    
    for (int i=0; i<=n; i++) {
        steps[i] = 0;
    }
    
    steps[1] = 1;
    steps[2] = 2;

    for (int i=3; i<=n; i++) {
        steps[i] = steps[i-1] + steps[i-2];
    }

    return steps[n];
}

int main() {
    int n = 10;
    
    printf("Number of ways to reach the top is %d\n", solve(n));

    return 0;
}

Output

Number of ways to reach the top is 89

Top down approach

//
//  main.cpp
//  Climbing steps
//
//  Created by Himanshu on 19/09/21.
//

#include <iostream>
using namespace std;
#define MAX 100


int solve (int n, int steps[]) {
    
    if (n <= 1) {
        return 1;
    } else if (n == 2) {
        return 2;
    }
    
    if (steps[n] == 0) {
        steps[n] = solve(n-1, steps) + solve(n-2, steps);
    }
    
    return steps[n];
}

int main() {
    int n = 10;
    int steps[n+1];
    
    for (int i=0; i<=n; i++) {
        steps[i] = 0;
    }
    
    printf("Number of ways to reach the top is %d\n", solve(n, steps));

    return 0;
}

Output

Number of ways to reach the top is 89

Practice Problem
Climbing Stairs [LeetCode]