Fibonnaci solution, constant time and space


  • 0
    L

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

    #include<cmath>
    using namespace std;
    class Solution {
    public:
        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
    O

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


  • 0
    L

    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
    M

    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.