Paint Fence
Medium · Dynamic Programming · Dynamic Programming
Problem
A fence has n posts in a row, and you have k paint colors. Every post is painted exactly one color, and no three or more consecutive posts may have the same color. Two posts in a row may share a color.
Return the number of ways to paint the fence. The inputs are chosen so the answer fits in a signed 32-bit integer.
Examples
Input: n = 3, k = 2 Output: 6
Two colors give 2^3 = 8 colorings of three posts; only the two single-color ones are ruled out.
Input: n = 1, k = 4 Output: 4
A single post can take any of the four colors.
Input: n = 4, k = 3 Output: 66
Rolling the counts: (same, diff) goes (0, 3), (3, 6), (6, 18), (18, 48), and 18 + 48 = 66.
Constraints
- 1 <= n <= 50
- 1 <= k <= 10^5
- The answer is at most 2^31 - 1.
Approaches
- Plain recursion on the last post — time O(φ^n), space O(n)
Follow-up
Adding the two states gives total[i] = (k - 1) * (total[i - 1] + total[i - 2]), a Fibonacci-like recurrence; with matrix exponentiation it can be evaluated in O(log n) for huge n (modulo a prime). If at most m equal posts may stand together, keep one state per run length 1..m.
Related problems
Start free on Cariara · Coding problems · System design studio
