/ Array

# Climbing Stairs Leetcode

##### Problem Statement

You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Given, there's stair case which can be climbed in 1 or 2 steps. So, at every step we have 2 choices to make. Let's see the number of ways you can climb the stairs starting from 0.

To make,

``````              n          No of steps required
0          0
1          1
2          2
3          3
4          5
.          .
.          .
n-2        n-3 + n-4
n-1        n-3 + n-2
n          n-1 + n-2
``````

The above sequence looks almost like a fibonocci sequence, where the number of ways you can climb n is the sum of the previous 2.

Based on this logic, we can simply put together a modified version of fibonocci to solve this.

``````class ClimbingStairs {
public static void main(String[] args){
int steps = 8;
int result = new ClimbingStairs().climbStairs(steps);
System.out.println("The number of ways to climb is "+result);
}
public int climbStairs(int n) {
if(n<=2) return n;
int oneStepBefore = 2;
int twoStepsBefore = 1;
int allWays = 0;

for(int i=2;i<n;i++){
allWays = oneStepBefore + twoStepsBefore;
twoStepsBefore = oneStepBefore;
oneStepBefore = allWays;
}
return allWays;
}
}

``````

The time complexity of the code is O(n) since we calculate value at every step to reach the final value.