# Python solution with explanation

• 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``````

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

}
``````

}

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

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

• 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
abb
bba

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

• @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
``````

• 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;
}
``````

• thanks for the explanation

• thanks for the explanation, it helps a lot!

• 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)

• Thanks, that makes a lot of sense.

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