LeetCode Blind 15/75: Climbing Stairs

Problem statement

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?
Link to problem

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

Solutions

Approach 1: Fibonacci Series

Randomly found this approach while I was drawing out different ways for 4, 5 and 6.

Apparently, it’s a Fibonacci sequence because:
For n = 2, it takes 2 steps
For n = 3, it takes 3 steps
For n = 4, it takes 5 steps
and so on

Now normally you would do this using a while loop and finding the nth fibonacci using $F_{n+1} = F_n + F_{n-1}$.

But I decided to do it differently and stumbled upon Binet’s Formula and The Golden Ratio and the formula is given as such:

Perhaps it’s not very visible in Dark Mode

Implementation in Rust

fn climb_stairs(mut n: i32) -> i32 {
    n = n + 1;

    let sqrt_five = (5 as f64).sqrt();
    let phi = (1.0 + sqrt_five) / 2.0;
    
    let f_n = (f64::powf(phi, n.into()) - f64::powf(1.0 - phi, n.into())) / sqrt_five;

    f_n as i32
}

Time Complexity: $O(1)$
Runtime on LeetCode: $0$ms

Other approach would be to brute force the solution using decision trees which can also be optimized using memoization but time complexity would be $O(n)$

Problem statement#

Solutions#

Approach 1: Fibonacci Series#

Problem statement

Solutions

Approach 1: Fibonacci Series