# Climbing Stairs Solution 1

By: J the Code Monkey
Posted: Jun 30, 2021 Updated: Jul 3, 2024

Climbing Stairs

Get the code & notes on

# Problem Description

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

Ex 1) Input: n = 2 Output: 2

Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Ex 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

# Thought Process

  • Let's start by diagramming the different ways we can climb the steps to see if we can find a pattern.

    • When n = 3 we have:
  • From the diagram we can see there are 3 distinct ways to climb to the top when n = 3 since we can ignore the scenarios where we take extra steps.

  • To help you see a pattern try drawing out more diagrams for larger values of n or creating a generalized diagram for any value of n.

  • The diagram above is an example of a recursion tree.

  • So, one way to solve this problem is to come up with a recursive formula that represents how many distinct ways we can climb the stairs.

  • Let's use the diagram to help us come up with our recursive formula.

  • We know we can either add 1 step or 2 steps each time we climb up the stairs, and we want to hit our target of n steps.

  • So, we need to keep track of how many steps we have taken which we can represent with the variable , where represents the current choice when climbing the stairs.

  • Initially, , here means we haven't made a choice to take 1 step or 2 steps yet.

  • Each time we climb the stairs we make one of the following choices:

  • Now, we'll let denote our function for climbing the stairs.

  • Here's how we can represent the different scenarios for climbing the stairs:

  • We're passing the + and our target value of steps to our function .

  • Now, we need to determine how many times we need to to call .

  • We know from the diagram if , then we can ignore that way of climbing the stairs

  • We also know if , then we have found a valid way to climb the steps.

  • Using this knowledge we can come up with the following:

# Implementation

var climbStairs = function(n) {
  return wayToClimb(0, n);
};

var wayToClimb = function(stepsTaken, n) {
  if (stepsTaken > n) {
    return 0;
  }

  if (stepsTaken === n) {
    return 1;
  }

  return wayToClimb(stepsTaken + 1, n) + wayToClimb(stepsTaken + 2, n);
};

let n = 4;
console.log(climbStairs(n));

# Downsides

  • Our solution will work, but it's not efficient.

  • We'll actually get a time limit exceeded error on LeetCode if we submit this.

  • This is because the time complexity of our solution is O(2n).

  • We can look at our recursion tree above and count the number of nodes to determine the time complexity.

  • Now, we won't count exactly 2n nodes since our recursive formula isn't exactly 2n, but when dealing with Big-Oh we only care about the behavior as n becomes very large.

  • We'll be improving this in the next post by drawing out recursion trees for larger values of n which will allow us to see an interesting pattern.

Made by & for Code Monkeys 🐵