Easiest java solution with O(1) space

  • 4
    public int numWays(int n, int k) {
        if(n < 1)   return 0;
        int sum1 = k, sum2 = 0;
        while(--n > 0){
            int temp = sum2;
            sum2 = sum1;
            sum1 = (sum1 + temp) * (k - 1);
        return sum1 + sum2;

    At a first glance, I just gave it a k * (int)Math.pow(n-1, k-1), until I saw the n=2 & k=1 wrong answer, and found it interesting. It's actually a DP problem, where sum1 is computing not same color in current node, and sum2 is painting the same color currently.

Log in to reply

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