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.