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