308. Painting the Fence Problem

Given a fence with n posts and k available colors, count the number of distinct ways to paint every post using one color per post such that no more than two adjacent posts share the same color.

Input: Two lines: the first contains n (number of posts), the second contains k (number of colors). Output: Print a single integer - the number of valid ways to paint the fence.

1 <= n <= 10^3, 1 <= k <= 10^3

The base cases (n=1 gives k, n=2 gives k²) are genuinely special and don't fit the general recurrence cleanly - always handle very small n explicitly before applying the general same/diff recurrence.

Count the ways to paint n fence posts with k colors so no more than two adjacent posts share a color. Brute force: Try every possible color assignment to all n posts directly (k^n total combinations) and filter for the no-three-consecutive-same rule - this is exponential, impractical for larger n. Optimised: Tracking the running 'same as previous' and 'different from previous' totals separately captures ALL the information needed to correctly extend the pattern by one more post - since 'same[i]' can ONLY come from a PREVIOUS 'diff' state (posting the SAME color twice in a row is only valid immediately after a color CHANGE, never after an already-matching pair), this recurrence directly enforces the no-three-in-a-row rule.

Recursively try every one of the k^n possible ways to assign a color to each of the n posts, and for each complete coloring, scan through it checking that no run of three or more consecutive posts shares the same color; count the colorings that pass. This directly checks the constraint against every possible coloring, but the number of colorings to check grows exponentially with n. Time: O(k^n) Space: O(n)

Use the standard recurrence: let same[i] count valid colorings of the first i posts where post i matches post i-1's color, and diff[i] count those where it differs. same[i] equals diff[i-1], since matching the previous post is only safe if that previous post itself just differed from its own predecessor (otherwise three would share a color), and diff[i] equals (k-1) times (same[i-1] + diff[i-1]), since any of the other k-1 colors can be chosen regardless of what came before. Memoizing these values as they're computed via top-down recursion ensures each is computed exactly once. Time: O(n) Space: O(n)

Compute the same same[i] and diff[i] recurrence iteratively from i=2 upward, but since each step only needs the previous step's same and diff values, keep just those two running totals in variables instead of full arrays. This removes both recursion overhead and the memoization table entirely. Time: O(n) Space: O(1)

1. Track two running totals: same[i] = ways where post i matches post i-1's color, and diff[i] = ways where it differs. 2. same[i] = diff[i-1] (only valid if post i-1 differed from post i-2, otherwise three-in-a-row would repeat); diff[i] = (same[i-1]+diff[i-1]) * (k-1). 3. Base cases: n==1 gives simply k; n==2 gives k*k.

Time: O(n) - one single pass building up same[] and diff[]. Space: O(1) - only the previous same/diff values need to be kept in memory.

Test n = 1 (answer is simply k) and n = 2 (answer is k*k), plus k = 1 or n and k both at their upper bound of 1000.

Be ready to explain WHY same[i] can only derive from diff[i-1] (never from same[i-1]) - this is the entire mechanism enforcing 'at most two adjacent, never three' and is the trickiest part of the recurrence to get right.