Skip to main content

Climbing Stairs

Problem​

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?

Examples​

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: n = 3
Output: 3
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≤451 \leq n \leq 45

Solution​

Intuition​

To calculate the number of ways to climb the stairs, we can observe that when we are on the nth stair, we have two options:

  • Either we climbed one stair from the (n-1)th stair
  • Or we climbed two stairs from the (n-2)th stair

By leveraging this observation, we can break down the problem into smaller subproblems and apply the concept of the Fibonacci series. The base cases are when we are on the 1st stair (only one way to reach it) and the 2nd stair (two ways to reach it). By summing up the number of ways to reach the (n-1)th and (n-2)th stairs, we can compute the total number of ways to climb the stairs. This allows us to solve the problem efficiently using various dynamic programming techniques such as recursion, memoization, tabulation, or space optimization.

Approach 1: Recursive​

A recursive approach solves the problem by breaking down the larger problem into smaller subproblems.

Implementation​

class Solution {
climbStairs(n) {
if (n === 0 || n === 1) {
return 1;
}
return this.climbStairs(n - 1) + this.climbStairs(n - 2);
}
}

Codes in Different Languages​

Written by @Vipullakum007
class Solution {
climbStairs(n) {
if (n === 0 || n === 1) {
return 1;
}
return this.climbStairs(n - 1) + this.climbStairs(n - 2);
}
}

Complexity Analysis​

Time Complexity: O(2x+y)O(2^{x+y})

  • In the worst case, each move (left or down) results in two recursive calls, leading to an exponential number of calls.

Space Complexity: O(x+y)O(x + y)

  • The space complexity is due to the maximum depth of the recursion stack.
tip

When choosing an approach, consider both time and space complexities. For smaller inputs, simpler approaches like recursion might be sufficient, but for larger inputs, optimized solutions like memoization, tabulation, or space-optimized tabulation are more efficient and practical. Always analyze the constraints and requirements of your problem to select the most appropriate method.


References​