Skip to main content

0070 - Climbing Stairs (Easy)

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

Problem Statement

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?

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: x = 8
Output: 2
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

Constraints:

  • 1 <= n <= 45

Approach 1: Fibonacci Series

We can apply the concept of Fibonacci Numbers to solve this problem. The number of ways to reach the nthn^{th} step is equal to the sum of ways of reaching (n1)th(n-1)^{th} step and ways of reaching (n2)th(n-2)^{th} step. The base cases for this problem are n=1n = 1 and n=2n = 2.

We can see that for n=1n = 1, the number of ways to reach the 1st1^{st} step is 11 and for n=2n = 2, the number of ways to reach the 2nd2^{nd} step is 22. Similarly, for n=3n = 3, the number of ways to reach the 3rd3^{rd} step is 33 and for n=4n = 4, the number of ways to reach the 4th4^{th} step is 55. This follows the Fibonacci Series(1, 2, 3, 5, 8, 13, ...).

Time Complexity: O(n)O(n), where nn is the number of steps to reach the top.

Space complexity: O(1)O(1)

Written by @aryankashyap7
class Solution {
public:
int climbStairs(int n){
// base cases
if (n < 4) return n;
// apply Fibonacci Series where a and b are the previous two numbers
int a = 2, b = 3;
int res = 0;
// calculate the number of ways to reach the n^{th} step
for (int i = 4; i <= n; i++) {
res = a + b;
// Updating the values of a and b
if (i % 2 == 0) a = res;
else b = res;
}
// return the number of ways possible
return res;
}
};