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

25 thoughts on “[Programming Problem] Paint Fence

  1. My husband and i ended up being very lucky that Edward managed to finish up his analysis through your ideas he made out of your site. It is now and again perplexing just to possibly be freely giving information which often other people may have been trying to sell. So we fully understand we’ve got you to appreciate because of that. The type of explanations you’ve made, the straightforward website navigation, the friendships your site help engender – it’s mostly terrific, and it’s facilitating our son and our family understand this content is fun, which is quite fundamental. Thank you for all the pieces!

  2. I must point out my affection for your kind-heartedness supporting those people that have the need for assistance with this niche. Your special commitment to getting the solution all-around had been pretty functional and have made guys just like me to attain their aims. The interesting recommendations entails so much to me and much more to my mates. Thanks a lot; from everyone of us.

  3. My spouse and i were quite thankful that Louis could conclude his homework through the entire ideas he got from your own web pages. It is now and again perplexing to just be offering tactics which people today might have been selling. And we also figure out we have got you to be grateful to for this. The entire explanations you made, the simple web site menu, the relationships you can assist to foster – it’s got everything wonderful, and it is aiding our son and the family believe that this concept is thrilling, and that’s exceedingly important. Thank you for the whole thing!

  4. I want to express thanks to the writer just for bailing me out of this particular instance. Because of surfing through the search engines and finding solutions that were not pleasant, I believed my entire life was done. Being alive minus the approaches to the difficulties you have sorted out by means of your main report is a critical case, as well as ones which may have negatively affected my career if I had not discovered your website. Your personal natural talent and kindness in maneuvering every part was tremendous. I am not sure what I would’ve done if I hadn’t encountered such a point like this. I am able to at this moment look forward to my future. Thanks a lot so much for this skilled and sensible help. I will not be reluctant to recommend the website to any individual who needs and wants guidance about this topic.

  5. I would like to point out my appreciation for your kindness supporting women who really want assistance with this particular subject matter. Your real commitment to getting the message throughout had been certainly functional and has constantly empowered professionals much like me to get to their objectives. Your own valuable report signifies a lot a person like me and much more to my office colleagues. Thank you; from everyone of us.

  6. I wanted to post you that very little remark to finally thank you so much over again on your awesome views you have documented on this page. This has been remarkably open-handed with people like you to provide publicly all many people would have sold as an ebook to help make some cash for themselves, notably since you might well have tried it in case you wanted. The points in addition worked to provide a fantastic way to comprehend most people have the same zeal the same as my very own to know a good deal more in regard to this issue. I’m sure there are many more fun situations in the future for those who view your site.

Leave a Reply

Your email address will not be published.