Painting Without Three In a Row
n fence posts are painted, each in one of k colours. No THREE consecutive
posts may share a colour, though two may. Print how many paintings are possible.
n = 3, k = 2 -> 6 of the 8 paintings, AAA and BBB are banned
The obstacle is that "is this post legal" depends on the two before it, so a
state of "how many ways to paint the first i posts" is not enough to continue.
The repair is to split that state by what just happened:
same[i] paintings of the first i posts whose last TWO posts match
diff[i] paintings of the first i posts whose last two posts differ
Now the step is forced. A new post matching its predecessor is only legal when
the last two differed, so same comes from diff. A new post differing from
its predecessor may follow either case, in k - 1 ways:
same[i] = diff[i-1]
diff[i] = (same[i-1] + diff[i-1]) * (k - 1)
Starting from same[2] = k and diff[2] = k * (k - 1), with n = 1 answering
k on its own.
Choosing WHAT TO REMEMBER is the whole exercise, and it is the skill that transfers. The table is trivial once the state is right, and impossible before.