245. Paint Fence
A row of n fence posts is waiting for paint, and your palette offers k colors. Each post ends up coated in one — and only one — of them, and the single rule is: no three consecutive posts may all share the same color. Two matching neighbors are allowed — a third in a row is not.
Given the integers n and k, return how many distinct valid paintings exist. The answer is guaranteed to fit in a signed 32-bit integer.
Example 1:
Input: n = 3, k = 2
Output: 6
Explanation: With colors A and B there are 2^3 = 8 paintings of 3 posts; only AAA and BBB break the rule, leaving 6.
Example 2:
Input: n = 2, k = 3
Output: 9
Explanation: Two posts can never form a run of three, so every one of the 3 × 3 = 9 paintings is valid.
Constraints:
- 1 ≤ n ≤ 50
- 1 ≤ k ≤ 10⁵
- The answer is guaranteed to fit in a signed 32-bit integer.
Hints:
Only the relationship between the last two posts matters. Classify every painting of the first i posts by whether post i matches post i - 1: keep two counts, same(i) and diff(i).
same(i) = diff(i - 1), because extending a matching pair with the same color again would make three in a row. diff(i) = (same(i - 1) + diff(i - 1)) * (k - 1), since any painting can continue with any of the other k - 1 colors. Start from i = 2 with same = k and diff = k(k - 1), and handle n = 1 separately (just k).
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: n = 3, k = 2
Expected output: 6