We define the function `numWays(n, k)`

to return the number of ways to paint n fences with `k`

colours such that the first fence is always just a `single`

colour and if the `first two`

fences are always a `single`

colour. i.e. Suppose we have 3 colours, (red, green, blue), then we assume that the first fence will always be red, and if the first 2 fences are of the same colour, they are always red.

Suppose the first fence is always red, then we can determine the number of ways to paint the remaining `n-1`

fences with colours (green, blue). This gives us `(k-1) * numWays(n-1)`

.

Suppose the first 2 fences are always red, then we can determine the number of ways to paint the remaining `n-2`

fences with colours (green, blue). This gives us `(k-1) * numWays(n-2)`

.

Hence, the total ways to paint `n`

fences with `k`

colours is `k * numWays(n, k)`

.

The code below probably won't pass the OJ since it's not memoized, but it's easy to memoize it.

```
int numWays(int n, int k) {
// Painting 2 fences such that either the 2nd fence alone
// is just a single colour, OR the first 2 fences are just a single
// colour is possible by painting the 2nd fence with 1 colour
// and the first fence with (k-1) colours, or both fences with
// the one colour. i.e. ((k-1) + 1) = k.
if (n == 2) return k;
if (n == 1) return 1; // Just painting 1 fence with 1 colour.
if (n < 1) return 0;
return (k-1) * (numWays(n-1, k) + numWays(n-2, k));
}
```