LeetCode: 276. Paint Fence

LeetCode: 276. Paint Fence

Summary

Return the number of valid ways to paint n fence posts using k colors.

Rules:

• Every post must be painted exactly one color.
• There cannot be three or more consecutive posts with the same color.

Approach

Use dynamic programming with two states:

• diff[i]: number of ways to paint up to post i where post i has a different color from post i-1.
• same[i]: number of ways to paint up to post i where post i has the same color as post i-1.

Transitions:

• diff[i] = (diff[i-1] + same[i-1]) * (k - 1)
• same[i] = diff[i-1]

Why:

• To make post i different, choose any coloring from i-1 and then choose one of k-1 different colors.
• To make post i the same, post i-1 must already be different from i-2; otherwise we would create three consecutive posts with the same color.

Function

Initialization:

• n: number of posts
• k: number of colors
• If n == 1, return k.
• diff = [k] (for the first post, all k colors are valid)
• same = [0]

For each i in range(n - 1):

• diff[i + 1] = (diff[i] + same[i]) * (k - 1)
• same[i + 1] = diff[i]

return diff[-1] + same[-1]

Edge case:

• If k == 1 and n >= 3, the answer is 0 (three consecutive posts would have the same color).
• If n <= 2, values are still valid under the rule.

Complexity

Time complexity: O(N), where N is the number of posts.
Space complexity: O(N) for diff and same.