Easy to understand Java O(n) runtime, O(1) space


  • 42

    w(n) number of ways to paint n posts

    p(n) color of the nth post

    w(n) consists of two cases:

    1.p(n) == p(n - 1)

    2.p(n) != p(n - 1)

    case 2 is easy. for every way of painting all previous (n - 1) posts, you have (k - 1) ways to paint p(n)
    because you can choose k - 1 different color rather than the same color as p(n - 1)

    so w(n - 1) * (k - 1)

    notice that for p(n) == p(n - 1), p(n - 1) must be not equal to p(n - 2), this is equalvalent to replace n by n - 1
    for the formular above, essentially the same as case2 but for a smaller n.
    so w(n - 1 - 1) * (k - 1)

    so w(n) = (k - 1) * (w(n - 1) + w(n - 2))

    public class Solution {
        public int numWays(int n, int k) {
            if ((n == 0 || k == 0) || (k == 1 && n >= 3))
                return 0;
            int w1 = k;
            int w2 = k * k;
            int w3; 
            if (n == 1)
                return w1;
            if (n == 2)
                return w2;
            for (int i = 0; i <= n - 3; i++) {
                w3 = (k - 1) * (w2 + w1);
                w1 = w2;
                w2 = w3;
            }
            return w2; // wrong if you return w3, w3 may not be initialized.
        }
    }

  • 0
    P

    I pretty had the same approach and ended up converting your code to python — returning w3 is perfectly fine. it's always initialized.

    class Solution(object):
        def numWays(self, n, k):
            """
            :type n: int
            :type k: int
            :rtype: int
            """
            if n == 0 or k == 0 or (k == 1 and n >= 3):
                return 0
    
            w1 = k
            w2 = k*k;
            if n == 1:
                return w1
            if n == 2:
                return w2
            w3 = 0
            for i in range(3, n+1):
                w3 = (k-1)*(w1 + w2)
                w1 = w2
                w2 = w3
            return w3

  • 0
    M

    Great solution, and concise, clear explanation.


  • 0
    L

    @xuyirui Neat explanation -- thank you.
    I'm not fully clear about the num_ways for case 1.

    Case 2: w(n) = w(n-1) * (k-1)
    Case1:
    p(n) == p(n-1) && p(n-1) != p(n-2)

    therefore, w(n) = w(n-1) * k // we can use k colors for n, multiplied by ways for n-1.
    since we know p(n-1) != p(n-2), we reduce this to
    w(n) = w(n-1-1) * (k-1) * k
    w(n) = w(n-2) * (k-1) * k.

    To summarize, i guess i couldn't understand case 1, where w(n) is just w(n-2) * (k-1) and not w(n-2) * (k-1) * k.


    Update:
    I think I see where I went wrong. keeping the post as is and updating, incase someone else made the same mistake.

    therefore, w(n) = w(n-1) * k // we can use k colors for n, multiplied by ways for n-1.

    This should be w(n) = w(n-1) * 1 // since we are painting n with the same color as n-1, essentially 1 choice and not k choices here.


Log in to reply
 

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