Fibonnaci solution, constant time and space

  • 0

    It is a DP problem, and from the DP recursion you can see that the solution is Fibonacci.
    Simply apply the Fib formula.

    using namespace std;
    class Solution {
        int climbStairs(int n) {
            double sqr5=sqrt(5), p1=(1+sqr5)/2, p2=1-p1;
            return (int)(.5+(pow(p1,n+1)-pow(p2,n+1))/sqr5);

  • 0

    but pow(x, n) may be O(logN), not O(1)

  • 0

    Well technically, you're right. But for all practical purposes, N is at most a 64-bit integer, and so pow is O(64) which is constant.

  • 0

    I just cannot understand why the power in the third solution is n+1 instead of n? Thank you.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.