mediumDynamic Programming 1DPure DSA~25 min
Ways to Paint a Fence Without Three in a Row
Paint a row of fence posts using k colors so that no three consecutive posts share the same color. Count the distinct colorings.
Problem
Given n posts and k colors, return the number of ways to paint the fence such that at most two adjacent posts have the same color.
Input
Two integers n (posts) and k (colors).
Output
An integer: the number of valid colorings.
Constraints
- 1 <= n <= 50
- 1 <= k <= 100
- No three consecutive posts may share a color.
Examples
Example 1
Input
n = 3, k = 2
Output
6
Of 8 colorings, the two all-same ones are invalid, leaving 6.
Example 2
Input
n = 1, k = 1
Output
1
One post, one color.