Climbing Stairs

How it works

The number of ways to climb stairs follows the Fibonacci sequence.
There is a closed-form mathematical formula (called Binet’s Formula) that directly computes the nth Fibonacci number using powers and square roots, without loops or recursion.

This works because Fibonacci numbers can be expressed using two constants derived from the golden ratio.

Steps

1. Compute the golden ratio φ = (1 + √5) / 2 and its conjugate ψ = (1 − √5) / 2.
2. Use Binet’s Formula to compute the Fibonacci value directly.
3. Since climbing stairs corresponds to Fib(n+1), adjust n accordingly.
4. Round the result to handle floating-point precision.

Complexity

• Time complexity: O(log n)
• Space complexity: O(1)

Things to watch for

Off-by-One Error in Base Cases

Initializing DP incorrectly or misunderstanding what dp[0] represents. For this problem, dp[1] = 1 (one way to climb 1 step) and dp[2] = 2 (two ways to climb 2 steps). Starting the loop from index 1 instead of 3 overwrites these base cases.

Not Handling n = 1 or n = 2 Edge Cases

Attempting to access dp[n-1] or dp[n-2] when n is 1 or 2 without proper base case handling, causing index out of bounds errors. Always check if n <= 2: return n before running the general loop.

import math

class Solution:
    def climbStairs(self, n: int) -> int:
        sqrt5 = math.sqrt(5)
        phi = (1 + sqrt5) / 2
        psi = (1 - sqrt5) / 2
        n += 1
        return round((phi**n - psi**n) / sqrt5)

class Solution {
public:
    int climbStairs(int n) {
        double sqrt5 = sqrt(5);
        double phi = (1 + sqrt5) / 2;
        double psi = (1 - sqrt5) / 2;
        n++;
        return round((pow(phi, n) - pow(psi, n)) / sqrt5);
    }
};