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); }`

// Return 1 for N lesser or equals to 1`int fib(int n, map<int, int>& l){`

`// Find N in look up table`

`if(n<=1) return 1;`

`// Compute fibonacci value of N`

`if (l.find(n)==l.end())`

`// Return stored Fibonacci number at N`

`l[n] = fib(n-1,l)+fib(n-2,l);`

`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 N^{th}Fibonacci number`return l[n];`

`}`

};

Applications of Fibonacci series in Computer algorithms:

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

I am a Software Developer and Learning Enthusiast.

I love to code and create awesome technologies.

Currently I am developing MATLAB Unit Test Framework at MathWorks.

Here, I share my personal learnings and experiences that I think will benefit you 😉