O(log n) solution


  • 0
    J

    Classic fibonacci:

    #define DIM 2
    struct M{
        int t[DIM][DIM];
        M(){
            for(int i = 0; i < DIM; i++){
                for(int j = 0; j < DIM; j++){
                    t[i][j] = 0;
                }
            }
        }
    };
    
    M operator *(const M& a, const M& b){
        M result;
        for(int i = 0; i < DIM; i++){
            for(int j = 0; j < DIM; j++){
                for(int k = 0; k < DIM; k++){
                    result.t[i][j] += a.t[i][k] * b.t[k][j];
                }
            }
        }
        return result;
    }
    M pot(const M& a, int p){
        if(p == 0){
            M result;
            for(int i = 0; i < DIM; i++){
                result.t[i][i] = 1;
            }
            return result;
        }
        if(p & 1){
            return a * pot(a, p - 1);
        } else{
            M temp = pot(a, p / 2);
            return temp * temp;
        }
        
    }
    class Solution {
    public:
        int climbStairs(int n) {
            if(n <= 1){
                return 1;
            }
            M baseMatrix;
            baseMatrix.t[0][0] = 1;
            baseMatrix.t[0][1] = 1;
            M fibMatrix;
            fibMatrix.t[0][0] = 0;
            fibMatrix.t[0][1] = 1;
            fibMatrix.t[1][0] = 1;
            fibMatrix.t[1][1] = 1;
            fibMatrix = pot(fibMatrix, n - 1);
            baseMatrix = baseMatrix * fibMatrix;
            return baseMatrix.t[0][1];
        }
    };

Log in to reply
 

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