This problem is not obvious to me (it is medium in my opinion). I spent quite some time, and came up an idea of dynamic programming approach. Let us use `p(n)`

to denote the color of post n, use `w(n)`

to denote the number of ways to paint post n, and use `r(n)`

to denote the returned number of ways to paint n posts.

```
for n == 0, return 0 or 1 # Up to you;
for n == 1, return k;
for n == 2,
if p(2) == p(1), then r(n)=k,
because the two have the same color.
if p(2) != p(1), then r(n)=k(k-1)
because w(1)=k, w(2)=k-1.
for n >= 3,
r(n) = r(n,when p(n)==p(n-1)) + r(n,when p(n)!=p(n-1))
```

When `p(n-1) == p(n)`

, we require `p(n-2) != p(n-1)`

. This is the same as if we are painting (n-1) posts and the last two posts have different colors, which means `same(n)=diff(n−1)`

.

When `p(n-1) != p(n)`

, we have `r(n−1)`

ways to paint the first n-1 posts, and `k−1`

ways to paint the n-th post. So `diff(n)=r(n−1)(k−1)`

.

Note that `r(n−1)`

is really just the sum of `same(n−1)`

and `diff(n−1)`

.

Code:

```
def paintFence(n, k):
if n == 0:
return 0
if n == 1:
return k
# Now n >= 2.
# Initialize same and diff as if n == 2
same = k
diff = k*(k-1)
for i in range(3,n+1):
r_prev = same + diff # r(i-1)
same = diff # same(i)=diff(i-1)
diff = r_prev*(k-1)
return same + diff
```