Improved from O(N) to O(lgN), exponentiating by squaring


  • 0
    G

    0_1501683058771_7e6f7e85-5d24-42f4-a06c-a453d11e1036-image.png
    Inspired by Leetcode 522 student attendance record ii.
    See what @lixx2100 said in Improving the runtime from O(n) to O(log n):

    This quick powering method can be applied to a lot of DP questions that only use O(1) memory, which means transform function can be written as DP[i] = A* DP[i-1], in which A is a matrix.

    class Solution {
    public:
        int numWays(int n, int k) {
            if(!k || !n) return 0;
            vector<int> dp({k, 0});
            vector<vector<int>> A({
                {k-1, k-1}, {1, 0}    
            });
            n -= 1;
            while(n > 0){
                if(n % 2 == 1){
                    vector<int> tmp = dp;
                    dp[0] = A[0][0] * tmp[0] + A[0][1] * tmp[1];
                    dp[1] = A[1][0] * tmp[0] + A[1][1] * tmp[1];
                }
                A = sq(A);
                n /= 2;
            }
            return dp[0] + dp[1];
        }
        
        vector<vector<int>> sq(vector<vector<int>>& A){
            vector<vector<int>> C(2, vector<int>(2, 0));
            for(int i = 0; i < 2; i ++){
                for(int j = 0; j < 2; j ++){
                    for(int k = 0; k < 2; k ++){
                        C[i][j] += A[i][k] * A[k][j];
                    }
                }
            }
            return C;
        }
    };
    

Log in to reply
 

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