Three different solutions


  • 1
    S
    // fibonacci sequence
    int climbStairs(int n) {
        if (n <= 2) return n;
        int a = 1, b = 2, c = 0;
        for (int i = 0; i < n-2; i++){
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }
    
    // dynamic programming
    int climbStairs(int n) {
        vector<int> s(n+1);
        return f(n, s);
    }
    
    int f(int n, vector<int> &s) { 
        if (s[n]) return s[n]; 
        return s[n] = n <= 2 ? n : f(n-1, s) + f(n-2, s);
    }
    
    // decomposition formula
    int climbStairs(int n) {
        return (pow((1 + sqrt(5)) / 2, n + 1) - pow((1 - sqrt(5)) / 2, n + 1)) / sqrt(5);
    }

  • 0
    T

    You don't need 3 variables (a, b and c) for fibonacci sequence. 2 is enough.


  • 0
    M

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


  • 0
    S

    you can just find the detail about fibonacci's decomposition formula


  • 0
    M

    Thank you. I see, the nth number in Binet's formula is actually F(n-1).


Log in to reply
 

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