Find distinct ways to climb the stairs in javascript.

An algorithm to find distinct ways to climb the stairs.

We will implement a simple algorithm in javascript to find distinct ways to climb the stairs. Everything will be written in ES6.

There are n stairs and you can climb either 1 or 2 steps at a time.

Example

Input:
2
3

Output:
2
//Explanation
//1 step + 1 step
//2 steps

3
//Explanation
//1 step + 1 step + 1 step
//2 steps + 1 step
//1 step + 2 steps

As this is a dynamic programming problem we will solve this problem with recursion and see the optimized solution as well.

Using Recursion.

Implementation

• We will create a function and call it recursively to solve the problem.
• We will use a temp variable and check if it is eqaul to the given steps.
• If it is eqaul then we will return 1 else if it is greater than given stairs then we will return 0.
• Call the same function recursively with 1 step and 2 steps and add their outputs.

let climbStairs = (n, count = 0) => {
   //if count is greater than stairs then return 0;
   if(count > n){
       return 0;
   }
   
   //if it is equal to the stairs then return 1.
   if(count === n){
       return 1;
   }   
   
   //cal the same function recursively with possible steps that can be taken.
   return climbStairs(n, count + 1) + climbStairs(n, count + 2);
};

Input:
console.log(climbStairs(5));
console.log(climbStairs(3));

Output:
8
3

Time complexity: O(2 ^ n).
Space complexity: O(n).

Time and Space complexity

• We call the same function recursively twice which is calling itself again twice and so on like T(n)=T(n+1)+T(n+2)+O(1), so Time complexity is O(2 ^ n) which is exponential.
• Recursive function are stored in call stack, so Space complexity is O(n).

This function works completely fine but it does a lot of unnecessary work by calling itself again and again with the same value.

                               fnc(0)
                               /    \
                           fnc(1)    fnc(2)
                          /   \       /   \
                    fnc(2)  fnc(3)  fnc(3) fnc(4)
                     /  \
                  fnc(3) func(4)

As you can see we are calling fnc(2) twice and fnc(3) thrice.
We can optimize this algorithm by storing the already computed function using Dynamic Programming.

Using Dynamic Programming.

Implementation

• We will create a function which will recursively call itself to compute the algorithm like implemented above.
• We will use an array to keep track of the already computed functions value.
• If the value for the given function already exits then we will return the value else we will call the same function recursively with lesser values and store it.

let climbStairs = (n, count = 0, memo = []) => {
   //if step is greater than stairs then return 0
   if(count > n){
       return 0;
   }
   
   //if step is eqaul to the stairs then return 1
   if(count === n){
       return 1;
   }
   
   //if the value is present for the given step then return it
   if(memo[count] > 0){
       return memo[count];
   }
   
   //compute the value for the given step and save it
   memo[count] = climbStairs(n, count + 1, memo) + climbStairs(n, count + 2, memo);

   return memo[count];
};

Time complexity: O(n).
Space complexity: O(n).

Time and Space complexity

• We are using memoization to optimize the recursive algorithm by storing the value of the already computed functions with given number i.e we are just calling the functions with distinct numbers, so Time complexity is O(n) where n is the no of stairs.
• We are trading memory for speed, so Space complexity is O(n).