leetcode paint fence

Tags: ,

There is a fence with n posts, each post can be painted with one of the k colors.

You have to paint all the posts such that no more than two adjacent fence posts have the same color.

Return the total number of ways you can paint the fence.

Note:
n and k are non-negative integers.

There are many solutions online, but the following is the easiest to understand. Thanks the author! https://discuss.leetcode.com/topic/31093/easy-to-understand-java-o-n-runtime-o-1-space

w(n) number of ways to paint n posts

p(n) color of the nth post

w(n) consists of two cases:

1.p(n) == p(n – 1)

2.p(n) != p(n – 1)

case 2 is easy. for every way of painting all previous (n – 1) posts, you have (k – 1) ways to paint p(n)
because you can choose k – 1 different color rather than the same color as p(n – 1)

so w(n – 1) * (k – 1)

notice that for p(n) == p(n – 1), p(n – 1) must be not equal to p(n – 2), this is equalvalent to replace n by n – 1
for the formular above, essentially the same as case2 but for a smaller n.
so w(n – 1 – 1) * (k – 1)

so w(n) = (k – 1) * (w(n – 1) + w(n – 2))