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.

If we add another fence to it, how many combinations of coloring are possible now that we have two fences in the picture? The first fence can be coloured in ‘k’ ways as seen in the previous step. For the second fence, we can either paint it with the same colour as the first fence or we can choose a different colour for it. If we choose the same colour as the first fence, the total number of ways for painting the fences is = ‘k’ and if we choose a different colour from the first fence, the total number of ways of painting the fences = k * (k-1), where ‘k’ is the number of ways of painting the first fence, and (k-1) is the number of ways of painting the second fence (since we no longer pick the colour chosen for fence 1, it turns to (k-1) for the second fence). Thus, the total number of ways of painting the two fences with same and different colours = k (same) + k*(k-1) (different).

If we move on to 3 fences, the third fence can either be painted with the same colour as the second fence (provided the first fence is of a different…