Python solution with explanation


  • 76
    O

    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
    M

    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];
        
    }
    

    }


  • 0
    P

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


  • 0

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


  • 0
    D

    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:
    aba
    bab
    Two adjacent:
    abb
    bba

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


  • 0

    @deivasigamani

    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
    R

    thanks for the explanation


Log in to reply
 

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