Leetcode Problem 276. Paint Fence

The problem states that there are ’n’ fences which can be coloured with one of the ‘k’ colours in such a way that not more than two adjacent fences have the same colour.

How do we go about solving this problem?

If we really think about it, this problem is closely related to counting.

Say we have just a single fence. In how many ways can we colour it with ‘k’ colours?

We can colour it in ‘k’ ways.