Paint the Fence
A fence has n posts and you have k colors. Paint every post one color so that no three posts in a row share a color (two in a row are fine). Return the number of valid ways to paint the fence.
Example 1
n 3
k 2
returns 6
Of the 8 colorings, the two with all equal are invalid, leaving 6.
Constraints
1 <= n <= 71 <= k <= 4
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Dynamic programming problems
- Shared Subsequence LengthMedium
- Trading With Rest DaysMedium
- Unique Binary Search TreesMedium
- Unique Grid PathsMedium
- Ways to Make ChangeMedium
- At Most K TradesHard
- Cheapest Order of CutsHard
- Count Wavy NumbersHard