# 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]