Description
You have n fence posts and k colors. Adjacent posts can have same color, but no more than 2 in a row. Return number of ways to paint.
Examples
Input:
n = 3, k = 2Output:
6Explanation:
The DP formula tracks two states: 'same' (current post matches previous) and 'diff' (current differs from previous). For each post i, same[i] = diff[i-1] (can only match if previous was different), and diff[i] = (same[i-1] + diff[i-1]) * (k-1). The total ways = same[n] + diff[n], which equals 6 for n=3, k=2.
Input:
n = 2, k = 3Output:
9Explanation:
With 2 posts and 3 colors, the first post has 3 choices and the second has 3 choices, so there are 9 valid colorings.
Input:
n = 4, k = 3Output:
66Explanation:
With 4 posts and 3 colors, the dynamic programming count gives 66 total valid colorings.
Constraints
- •
1 ≤ n ≤ 50