# [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.

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; }```