# # Climbing Stairs Solution 1

Posted: Jun 30, 2021 Updated: Apr 18, 2023

Climbing Stairs

Get the code & notes on

Ask Questions & Share Solutions in

## # 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

## # 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.