# Climbing Stairs Solution 1

By: J the Code Monkey

•Posted: Jun 30, 2021 •Updated: Jul 3, 2024

# Links

Climbing Stairs

Problem 💡

Get the code & notes on

GitHub 💻

# 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(2ⁿ).
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 2ⁿ nodes since our recursive formula isn't exactly 2ⁿ, 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.