Paint Fence

easy dp

Problem

There are n posts and k colors. You cannot have three or more consecutive posts of the same color. Return the number of ways to paint the fence.

Inputn = 3, k = 2

Output6

With k=2 and n=3, allowed patterns: 112, 121, 122, 211, 212, 221.

def num_ways(n, k):
    if n == 0: return 0
    if n == 1: return k
    same, diff = k, k * (k - 1)
    for i in range(3, n + 1):
        same, diff = diff, (same + diff) * (k - 1)
    return same + diff

function numWays(n, k) {
  if (n === 0) return 0;
  if (n === 1) return k;
  let same = k, diff = k * (k - 1);
  for (let i = 3; i <= n; i++) {
    [same, diff] = [diff, (same + diff) * (k - 1)];
  }
  return same + diff;
}

class Solution {
    public int numWays(int n, int k) {
        if (n == 0) return 0;
        if (n == 1) return k;
        int same = k, diff = k * (k - 1);
        for (int i = 3; i <= n; i++) {
            int ns = diff;
            int nd = (same + diff) * (k - 1);
            same = ns; diff = nd;
        }
        return same + diff;
    }
}

int numWays(int n, int k) {
    if (n == 0) return 0;
    if (n == 1) return k;
    int same = k, diff = k * (k - 1);
    for (int i = 3; i <= n; i++) {
        int ns = diff, nd = (same + diff) * (k - 1);
        same = ns; diff = nd;
    }
    return same + diff;
}

Explanation

We paint n posts with k colors and the only rule is: never three same-colored posts in a row. The clever idea is to split the count at each post into two buckets — same = ways where this post matches the one before it, and diff = ways where it differs.

The base for two posts: same = k (pick any color and repeat it) and diff = k * (k - 1) (any first color, then a different second).

Each new post updates these. The new same can only come from the previous diff — because if the last two already matched, a third match would break the rule, so the post we extend must have differed. The new diff is every previous arrangement (same + diff) times the k - 1 colors that aren't the previous one.

Example: n = 3, k = 2. The 6 valid patterns are 112, 121, 122, 211, 212, 221, so the answer is 6, which equals same + diff after the loop.

Since each step only needs the two previous totals, this runs in linear time with constant memory.

Time: O(n) Space: O(1)