How to Solve ‘Climbing Stairs – Leetcode’ in Ten Seconds?

Climbing Stairs Leetcode is one of the popular programming questions asked in many interviews. Let us take a look at the same.

Imagine you are playing the game of climbing stairs. It takes ‘N’ steps to reach the topmost staircase. There is only one rule for this game – You can only take 1 or 2 steps at a time. Earlier you reach the top greater is the reward. Now as programming geeks we decide to create a logic that calculates the total number of ways we can climb to the top. This is described in the ‘Climbing Stairs’ problem on LeetCode.

Here let’s assume that N is 3, There can be 3 distinct ways to reach the top. which are:
– 1 + 1 + 1
– 2 + 1
– 1 + 2
Input = 3 Output = 3

For N equals to 4, There wil be 5 distinct ways. Which are:
– 1 + 1 + 1 + 1
– 2 + 2
– 2 + 1 + 1
– 1 + 2 + 1
– 1 + 1 + 2
Input = 4 Output = 5

For N equals 5, There will be 8 distict ways. Which are:
– 1 + 1 + 1 + 1 + 1
– 2 + 2 + 1
– 1 + 2 + 2
– 2 + 1 + 2
– 1 + 1 + 1 + 2
– 1 + 1 + 2 + 1
– 1 + 2 + 1 + 1
– 2 + 1 + 1 + 1
Input = 5 Output = 8

Now if we closely observe the pattern in inputs and outputs for every N we can see that this is Fibonacci series pattern and we have to essentially find N^th Fibonacci number.

To find the N^th Fibonacci number we can use a recursive approach or use dynamic programing approach with memoziation.

In recursion will follow the top to bottom approach we start with N and call the Fibonacci function to recursively compute the value. But with normal recurssion we will take lots of time to compute the N^th Fibonacci number. Inorder to speed up calculations we create a look up table and store all the computed values. The pseudo code for the recursive approach with look up table is as follows:
– Start
– Pass value of N to fib()
– If N equals 1 return N
– If N is not present in present in look up table
– Make a recursive call to comput N^th Fibonacci number and store in look up table
– Return the value of N^th Fibonacci number from look up table.
– Stop

C++ implementation of the recursive approach with look up table towards climbing stairs problem is as follows:

 class Solution {
  public:
    int climbStairs(int n) {
    // Look up table to store precomputed values
      map<int, int> look_up;
        return fib(n, look_up);
    }
      int fib(int n, map<int, int>& l){
     // Return 1 for N lesser or equals to 1
     if(n<=1) return 1;
     // Find N in look up table
     if (l.find(n)==l.end())
       // Compute fibonacci value of N
       l[n] = fib(n-1,l)+fib(n-2,l);
     // Return stored Fibonacci number at N
     return l[n];
   }
 };

Alternative approach would be to build the Fibonacci series bottom up and store the values in look up table and return the value of N^th Fibonacci number. The psuedo code for the bottom up approach is as follows:
– Start
– Compute base values of Fibonacci series. (0 – 3)
– Loop in till N to find all the values of Fibonacci series.
– Return the N^th Fibonacci number.
– Stop

C++ implementation of the Bottom up approach towards Climbing stairs problem is as follows:

class Solution {
  public:
    int climbStairs(int n) {
      // Look up table to store the Fibonacci numbers
      map<int, int> look_up;
      return fib(n, look_up);
    }

    int fib(int n, map<int, int>& l){
      // Return N for N <= 3
      if(n <= 3)
        return n;
      // Calculate base values of Fibonacci series
      for(int i=0; i<4; ++i)
        l[i] = i;
      // Calculate Fibonacci numbers till N
      for(int i=4; i<=n; ++i)
        l[i] = l[i-1]+l[i-2];
      // Return value of Nth Fibonacci number
      return l[n];
    }
 };

Applications of Fibonacci series in Computer algorithms:

• Fibonacci Search Technique
• Fibonacci Heap
• Fibonacci Cubes (graph) etc,.