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:
6 valid colorings.
Input:
n = 2, k = 3Output:
6Explanation:
With 2 posts and 3 colors, it is possible to paint the first post in 3 ways. For the second post, it is possible to use any of the 2 remaining colors (different from the first). Total: 3 × 2 = 6 valid colorings.
Input:
n = 4, k = 3Output:
66Explanation:
With 4 posts and 3 colors, using dynamic programming. First post: 3 ways. Second post: 3 × 2 = 6 ways (must differ from first). For posts 3 and 4, ensuring no 3 consecutive posts have the same color, giving us 66 total valid colorings.
Constraints
- •
1 ≤ n ≤ 50