Paint Fence

Count the number of ways to paint n fence posts with k colors such that no more than two adjacent posts have the same color. This is a dynamic programming problem where you derive a recurrence by tracking configurations that end with the same color as the previous post versus a different color.