70. Climbing Stairs

Climbing Stairs

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?

 

Example 1:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 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

 

Constraints:

• 1 <= n <= 45


Approach) Recursion

Solving this problem does not require an understanding of Fibonacci numbers. The Fibonacci numbers are the numbers in the next integer sequence.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ........

Fn = Fn-1 + Fn-2

Recursion is often used to solve the problem, but it is not very efficient with large Fibonacci numbers, and the complexity of such a program can be very disappointing.
Therefore, we will use dynamic programming.

Recursive solution example:

 function fib(n) {
    if (n <= 1)
        return n;
    return fib(n-1) + fib(n-2);
}

Dynamic programming is basically an optimization of regular recursion. Wherever we see a recursive solution, we can optimize it with dynamic programming. The idea is to simply store the results of the subtasks so that we don't have to recalculate them later when needed. This simple optimization reduces the time complexity from exponential to polynomial.

So, instead of recursing, we'll create variables with the first Fibonacci numbers (1, 1), not including 0, and with a simple iteration, we'll update them until we get what we want.

We also add a check, if the values are less than 4, return n, since the Fibonacci number 1 is '1', 2 is '2', 3 is '3', and only starting from 4, we will get a distinctive value.

var climbStairs = function(n) {
    if (n < 4) return n;
    let a = 1, b = 1, fib;
    for(let i = 2; i <= n; i++) {
        fib = a + b;
        a = b;
        b = fib;
    }
    return fib;
};

Time complexity: O(n)
Extra space: O(1)

This solution looks more understandable but takes up more space than the first one.

var climbStairs = function(n) {
    if (n < 4) return n;
    let fib = [1, 1];
    for (let i = 2; i <= n; i++) {
        fib[i] = fib[i - 1] + fib[i - 2];
    }
    return fib[n];
};

Time complexity: O(n) for given n;
Auxiliary space: O(n);

Also, to obtain Fibonacci numbers, you can use the matrix method, it is considered one of the most effective.

const mul = (
    [[a1, a2],[a3, a4]],
    [[b1, b2],[b3, b4]]) =>
    [[a1 * b1 + a2 * b3, a1 * b2 + a2 * b4],
     [a3 * b1 + a4 * b3, a3 * b2 + a4 * b4]];

const matrix = [[0, 1],[1, 1]];

const id = [[1, 0],[0, 1]]

var climbStairs = function(n) {
    let result = id;
    const bits = (n + 1).toString(2);

    for(const bit of bits){
        result = mul(result, result);
        if(bit === "1"){
            result = mul(result, matrix);
        }
    }
    return result[1][0];
}

Time complexity: O(Log n)
Additional space: O(Log n)

Conclusion

That’s all folks! In this post, we solved LeetCode problem 70. Climbing Stairs

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!