[Programming Problem] Paint Fence

You are painting a fence of n posts with k different colors. You must paint the posts following these rules:

  • Every post must be painted exactly one color.
  • At most one pair of adjacent fence posts can have the same color.

Given the two integers n and k, return the number of ways you can paint the fence.

[Link]

The recursive solution times out! So let’s think of a dynamic programming solution!

Single Fence
opt(0) = k options

Double Fence
opt(1) = k^2 options

Third Fence
When first two fences are same color: k * (k-1) = opt(0) * (k-1)
When first two fences are diff color: k * (k-1) * k = k^2 * (k-1) = opt(1) * (k-1)
opt(2) = opt(0) * (k-1) + opt(1) * (k-1)

Nth Fence??
opt(i) = opt(i-2) * (k-1) + opt(i-1) * (k-1)

/**
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
 
var numWays = function(n, k) {
    if (n===0) return 0;
    if (n===1) return k;
 
    const dp = new Array(n);
    dp[0] = k;
    dp[1] = k*k;
 
    for (let i = 2; i < n ; i++ ) {
        dp[i] = (dp[i-2] * (k-1)) + (dp[i-1] * (k-1));
    }
 
    return dp[n-1];
};

The recursive solution (this will timeout).

/**
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
 
var numWays = function(n, k) {
    if (n <= 2) return Math.pow(k, n);
    return countForOneColor([], 0, n, k);
};
 
var countForOneColor = function(curr, level, n, k) {
    if (level === n) return 1;
    let ret = 0;
    for (let i = 0 ; i < k ; i++) {
        if (level >= 2 && curr[level-1] === curr[level-2] && i === curr[level-1]) continue;
        curr[level] = i;
        ret += countForOneColor(curr, level+1, n, k);
        curr.pop();
    }
    return ret;
}

2,536 thoughts on “[Programming Problem] Paint Fence