Python solution with explanation

  • 94

    If n == 1, there would be k-ways to paint.

    if n == 2, there would be two situations:

    • 2.1 You paint same color with the previous post: k*1 ways to paint, named it as same
    • 2.2 You paint differently with the previous post: k*(k-1) ways to paint this way, named it as dif

    So, you can think, if n >= 3, you can always maintain these two situations,
    You either paint the same color with the previous one, or differently.

    Since there is a rule: "no more than two adjacent fence posts have the same color."

    We can further analyze:

    • from 2.1, since previous two are in the same color, next one you could only paint differently, and it would form one part of "paint differently" case in the n == 3 level, and the number of ways to paint this way would equal to same*(k-1).
    • from 2.2, since previous two are not the same, you can either paint the same color this time (dif*1) ways to do so, or stick to paint differently (dif*(k-1)) times.

    Here you can conclude, when seeing back from the next level, ways to paint the same, or variable same would equal to dif*1 = dif, and ways to paint differently, variable dif, would equal to same*(k-1)+dif*(k-1) = (same + dif)*(k-1)

    So we could write the following codes:

        if n == 0:
            return 0
        if n == 1:
            return k
        same, dif = k, k*(k-1)
        for i in range(3, n+1):
            same, dif = dif, (same+dif)*(k-1)
        return same + dif

  • 1

    Thanks for the explanation

    here's a java code for this

    public class Solution {
    public int numWays(int n, int k) {
        if(n == 0) return 0;
        if(n == 1) return k;
        int[] same = new int[n+1];
        int[] diff = new int[n+1];
        same[2] = k;
        diff[2] = k*(k-1);
        for(int i=3;i<=n;i++){
            same[i] = diff[i-1];
            diff[i] = same[i-1]*(k-1) + diff[i-1]*(k-1);
        return diff[n] + same[n];


  • 1

    Not really. You don't need to use O(n) space

  • 0

    Very detailed explanation even though for this easy question! Thank you!

  • 0

    for n=3 and k = 2 how come there are 6 solutions? I can think of only 4 solutions. Assuming a and b are the paint colors,

    All different:
    Two adjacent:

    is there any combination I am missing? Could someone help me understand the problem?

  • 0


    It's easier to think in base k and follow ascending order

    aab  112
    aba  121
    abb  122
    baa  211
    bab  212
    bba  221

  • 1

    C# version

        public int NumWays(int n, int k) 
            if (n == 0 || k == 0) return 0;
            if (n == 1) return k;
            int same = 0;
            int diff = k;
            int count = 1;
            while (count++ < n)
                int diffTemp = diff;
                diff = same * (k-1) + diff * (k-1);
                same = diffTemp;
            return same + diff;

  • 0

    thanks for the explanation

  • 0

    thanks for the explanation, it helps a lot!

  • 1

    Its easier to think in terms of state transition diagram. Every post i can end in diff state or same state. Think of the state transition between i-1 and i.

    1. If prev state was diff, then current state can end in diff or same.
      diff(i-1) -> diff(i)
      diff(i-1) -> same(i)

    2. If prev state was same then current state can only end in diff.
      same(i-1) -> diff(i)

  • 0

    Thanks, that makes a lot of sense.

Log in to reply

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