LeetCode Climbing Stairs: DP vs Closed Form of Result

Overview

This LeetCode Climbing Stairs can be reduced to find the n-th number in Fibonacci Sequence, DP is the most common solution while closed form can be found too.

LeetCode Climbing Stairs Problem

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

DP vs Closed From of Result

This is a very simple dp problem, consider the last steps we could take, we could take either 1 or 2 steps to reach the top, let f[n] denote   the number of different ways we climb to step n, then we have f[n] = f[n-1] + f[n-2], that is, we could take either 1 or 2 steps to reach n, obviously, this is the same formula as Fibonacci numbers, it could be solved in linear time and in constant space. The following is the code accepted by LeetCode OJ to pass this Climbing Stairs problem:

int climbStairs(int n) {
    if (n <= 1) return 1;
    int a = 1, b = 1, c = 1;
    for (int i = 2; i <= n; ++i) {
        c = a + b;
        a = b;
        b = c;
    }
    return c;
}
Furthermore, mathematically, we do have a closed form formula for calculating the n-th number in the Fibonacci sequence:
F_n = \frac{\varphi^n-\psi^n}{\varphi-\psi} = \frac{\varphi^n-\psi^n}{\sqrt 5}
where
\varphi = \frac{1 + \sqrt{5}}{2} \approx 1.61803\,39887\cdots\,     \psi = \frac{1 - \sqrt{5}}{2} = 1 - \varphi = - {1 \over \varphi} \approx -0.61803\,39887\cdots

So the following is the implementation based on the above formula F(n) = ( phi^n – (1-phi)^n ) / sqrt(5) which is also accepted by LeetCode OJ and can pass all the test cases for this Climbing Stairs problem:

int climbStairs(int n) {
    ++n;
    double root5 = sqrt(5);
    double phi = (1 + root5)/2;
    return (int)floor( ( pow(phi, n) - pow(1 - phi, n) ) / root5 );
}

Note two things:

  1. ++n at the first line, why?
  2. the time complexity is O(logN), why? Please refer my old post “LeetCode Pow(x, n): Binary Search vs Bit Decomposition” for the reasoning behind the scene.

Summary

This LeetCode Climbing Stairs can be reduced to find the n-th number in Fibonacci Sequence, DP is the most common solution while closed form can be found too.

Written on April 14, 2013