Paint Fence

Paint Fence

What is this problem about?

The Paint Fence problem asks you to count the number of ways to paint n fence posts with k colors such that no more than 2 consecutive posts have the same color. This coding problem uses DP with two states: same-color (current matches previous) and different-color (current differs from previous). The dynamic programming interview pattern is cleanly demonstrated.

Why is this asked in interviews?

Meta, Snowflake, and Google ask this because it's a clean DP problem where the constraint "at most 2 consecutive same colors" leads to a simple two-state recurrence. It validates DP state design for sequence coloring problems.

Algorithmic pattern used

Two-state DP. same[i] = ways to paint first i posts where post i has same color as post i-1. diff[i] = ways where post i has different color from post i-1. Recurrences: same[i] = diff[i-1] (can only extend different with same); diff[i] = (same[i-1] + diff[i-1]) * (k-1) (any previous state × k-1 choices). Answer = same[n] + diff[n].

Example explanation

n=3, k=2. Base: same[2]=2(k choices same), diff[2]=2(k choices, each has 1 different... wait: same[2]=k (all k colors for post 1, then same)? Let me recalculate:

• Post 1: same[1]=0 (no previous), diff[1]=k.
• Post 2: same[2]=diff[1]=k. diff[2]=(same[1]+diff[1])(k-1) = k(k-1).
• Post 3: same[3]=diff[2]=k(k-1). diff[3]=(same[2]+diff[2])(k-1) = k(1+(k-1))(k-1) = k(k-1)^2? = (k + k(k-1))(k-1) = kk(k-1) = k²(k-1). Total = k(k-1) + k²(k-1) = k(k-1)(1+k) = k(k²-1). For k=2, n=3: 2*3=6.

Common mistakes candidates make

• Not initializing base cases correctly.
• Allowing 3+ consecutive same colors (same[i] = diff[i-1] prevents this since same then same would require same[i] from same[i-1]).
• Off-by-one in the recurrence (starting from post 1 vs post 2).
• Using one-state DP (insufficient to capture the constraint).

Interview preparation tip

Two-state DP problems where "current state depends on whether previous was same or different" are common in sequence coloring and tiling. Always define states to capture the relevant history. Here, knowing whether the last two posts were same or different is sufficient to enforce the "at most 2 consecutive same" constraint. Practice Paint Fence I, then extend to k-consecutive limit variants.