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 

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 argc, const char * argv[]) {
    int n = 10;
    
    cout<<printf("%d\n", solve(n));
    return 0;
}

Output

Number of steps 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 argc, const char * argv[]) {
    int n = 10;
    int steps[n+1];
    
    for (int i=0; i<=n; i++) {
        steps[i] = 0;
    }
    
    printf("Number of steps to reach the top is %d\n", solve(n, steps));
    return 0;
}

Output

Number of steps to reach the top is 89

Practice Problem
Climbing Stairs [LeetCode]

Leave a Reply