C O(1) solution, one line, 0ms


  • 0
    int climbStairs(int n) {
        return (int)(1/sqrt(5)*(pow((1+sqrt(5))/2,n+1)-pow((1-sqrt(5))/2,n+1)));
    }
    

    Is Fibonacci, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …
    0_1474222120746_QQ拼音截图未命名.png
    In our case, is 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …
    So, replace n with n+1

    or

    int climbStairs(int n) {
        int n_1 = 1;
        int n_2 = 0;
        int tmp;
        for(int i=1; i<=n; i++){
            tmp = n_1+n_2;
            n_2 = n_1;
            n_1 = tmp;
        }
        return tmp;
    }
    

    according to:
    0_1474222816006_QQ拼音截图未命名.png


Log in to reply
 

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