There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

 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

This problem was taken from Leetcode

The solution:

Let’s look at the possible scenarios:

[table id=1 /]

If we look at the # of ways to climb, we clearly see that the ways to climb grows in Fibonacci sequence: 1, 2,  3,  5,  8,  13, 21

Then all we need to do is to iterate n times (where n  is the number of stairs) and to find the corresponding Fibonacci number.

Using while loop

• basically we use temp to store previous Fibonacci number temp = a , initially 1
• then we calculate the next number a = a + b , initially a = 0 + 1
• then we set up b = temp which stores the last Fibonacci number in order to be ready for the next iteration. Initially 1.

Looking at the numbers from the first iteration, it is clear that on the second one we will have:
temp = a = 1
a = a + b = 1 + 1 = 2
b = temp = 1

third iteration will produce:
temp = a = 2
a = a + b = 2 + 1 = 3
b = temp = 2
forth iteration:
temp = a = 3
a = a + b = 3 + 2 = 5
b = temp = 3

and so on … a will always return the Fibonacci number for the current n position.

Java Script

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    if( n < 4) 
        return n;

    fibonacci = function(n) {

        var a = 1, b = 0, temp, num = 1;

        while(num <= n) {
            temp = a;
            a = a + b;
            b = temp;
            num ++;
        }
        return a;
    }

    return fibonacci(n);
};

Using For loop

This is the easiest to comprehend:

• we create an array to store the Fibonacci numbers var fn = [1,1] with the first two numbers pre-set so the for loop could generate the next one.
• created for loop that picks the fn[i - 1] and fn[i - 2] numbers and generate the next one.
• pushed newly calculated Fibonacci number into an array so we could use to generate next one.
• keep looping till we reached i < n + 1 which is the  answer.

Java Script

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    if( n  < 3)
    return n;
    
    var fn = [1,1];
    for(var i = 2; i < n + 1; i ++) {
        var nextNumber = fn[i - 1] + fn[i - 2]; 
        fn.push(nextNumber);
    }

    return fn[fn.length - 1];
};

Third solution: Using recursive function.

Java Script

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    if( n < 4) 
        return n;

    fibonacci = function(n) {
        if(n < 2) {
            return n;
        }
        var result = fibonacci(n - 1) + fibonacci(n - 2);        
        return result;
    }

    return fibonacci(n + 1);
};

The idea here is to call fibonacci(n) function to generate the next Fibonacci number.
For n < 2 the function will simply return n 0,1,2.
For n = 3 the function will call itself recursively asking for previous two Fibonacci numbers (2 and 1) and will calculate the next number which is the sum of the previous two, and so on.

Optimize the recursive function to use Memoization.

Memoization is simple technique where we are storing the value of already computed parameter into a HashMap function and quickly retrieve it when we need it.

In our current example since the keys are just a numbers we could store the Fibonacci numbers in a regular array (line 9). Then we simply check if the value already is set up into memo array and return it or call fibonacci function once again.
Then we set up memo array with the next solved Fibonacci number with index n

Java Script

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    if( n < 4) 
        return n;

    var memo = [];
    fibonacci = function(n) {
        if(n < 2) {
            return n;
        }
        var a = memo[n - 1] ? memo[n - 1] : fibonacci(n - 1);
        var b = memo[n - 2] ? memo[n - 2] : fibonacci(n - 2);

        return memo[n] = a + b;
    }

    return fibonacci(n + 1);
};

You might also want to check Fibonacci sequence generator.