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.