# 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, S = 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;
steps = 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

https://leetcode.com/problems/climbing-stairs/submissions/