C++ implementation, constant memory and O(n) time


  • 2
    L
     int numWays(int n, int k) {
        if (n == 0) return 0;
        if (n <= 2) return pow(k, n);
        int same = k, notSame = k * (k-1);
        for(int i=3; i <= n; ++i){
            int oldSame = same;
            same = notSame;
            notSame = (oldSame + notSame) * (k-1);
        }
        return same + notSame;
    }

Log in to reply
 

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