You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
LeetCode-70: You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
The problem is similar to fibonacci series. The number of ways to reach the i-th step is the sum of the ways to reach the i-1 step and the i-2 step. The base cases are steps[0] = 1 and steps[1] = 1.
Based on the approach mentioned above, following is a java implementation:
public int climbStairs(int n) {
if (n < 2) {
return 1;
}
// initialize the steps array with base cases
int[] steps = new int[n + 1];
steps[0] = 1;
steps[1] = 1;
// calculate the number of ways to reach the i-th step
// as the sum of the ways to reach the i-1 and i-2 steps
for (int i = 2; i <= n; i++) {
steps[i] = steps[i - 1] + steps[i - 2];
}
return steps[n];
}
We can also optimize the space complexity by using only two variables to store the number of ways to reach the i-1 and i-2 steps.
public int climbStairs(int n) {
if(n < 2){
return 1;
}
// initialize the first and second
// variables with base cases
int first = 1;
int second = 1;
int steps = 0;
// calculate the number of ways to reach the i-th step
// as the sum of the ways to reach the i-1 and i-2 steps
for(int i=2; i <= n ; i++){
steps = first + second;
first = second;
second = steps;
}
return steps;
}
The time complexity for the above approach is \(O(n)\).
Also, depending on the approach, the space complexity can be:
Be notified of new posts. Subscribe to the RSS feed.