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

softwareeveryday

63 thoughts on “[Programming Problem] Paint Fence”

  18. 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!

    Reply

  19. 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.

    Reply

  21. 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!

    Reply

  22. 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.

    Reply

  23. 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.

    Reply

  24. 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.

    Reply

  26. I’m writing to let you understand what a awesome encounter my princess obtained checking the blog. She came to find plenty of issues, including what it’s like to have an amazing helping nature to get many others easily fully understand some grueling subject matter. You truly did more than my expected results. I appreciate you for displaying these interesting, trusted, revealing and as well as fun guidance on the topic to Sandra.

    Reply

  27. I wanted to post you that very small observation to help give thanks over again about the fantastic suggestions you’ve featured on this site. It is simply tremendously open-handed of you to allow freely exactly what a number of people could possibly have offered as an electronic book to make some bucks on their own, principally considering that you could possibly have done it in case you considered necessary. These good ideas in addition acted like a great way to realize that the rest have similar interest similar to my own to know a great deal more when considering this matter. I know there are thousands of more pleasant situations ahead for many who scan through your site.

    Reply

  28. I wanted to post you a bit of note to finally give thanks over again with the fantastic advice you’ve shown in this article. It has been certainly particularly open-handed of you to convey publicly all that most of us could have sold as an e-book to end up making some dough on their own, chiefly seeing that you could possibly have tried it if you considered necessary. The principles as well acted to provide a good way to realize that other people online have a similar dreams really like my own to see a good deal more when it comes to this matter. I am certain there are a lot more pleasant periods ahead for folks who check out your site.

    Reply

  34. I have to voice my affection for your kind-heartedness for those individuals that must have help on your theme. Your personal dedication to getting the message all around ended up being incredibly helpful and have in every case encouraged people much like me to get to their endeavors. Your new helpful guide signifies so much to me and much more to my office workers. Many thanks; from each one of us.

    Reply

  35. I wish to express my love for your kindness for persons that need help with in this situation. Your personal commitment to passing the message across has been incredibly invaluable and have frequently permitted girls much like me to realize their targets. Your new warm and friendly help indicates a lot to me and somewhat more to my fellow workers. Many thanks; from all of us.

    Reply

  36. I simply desired to appreciate you once again. I am not sure what I would have tried without the type of techniques revealed by you about such a concern. This has been a very daunting issue for me personally, nevertheless seeing the very skilled avenue you handled it took me to jump for gladness. I will be grateful for your service and hope you comprehend what an amazing job you are always doing educating many people through the use of your websites. Most likely you have never encountered any of us.

    Reply

  37. I am just commenting to let you know what a remarkable experience our child had using the blog. She realized plenty of pieces, with the inclusion of what it is like to have a marvelous giving nature to have many people without difficulty grasp chosen advanced things. You truly did more than our expected results. Thanks for producing these beneficial, safe, edifying and in addition easy thoughts on the topic to Emily.

    Reply

  38. I needed to write you one little bit of observation to finally thank you over again with the breathtaking opinions you’ve shared in this article. It is so pretty open-handed of you to give extensively precisely what most of us might have made available for an e-book to make some dough on their own, especially since you could possibly have done it in case you desired. Those suggestions likewise worked to provide a easy way to be sure that other individuals have the identical eagerness really like my personal own to understand a good deal more with regards to this matter. I am certain there are lots of more pleasurable sessions ahead for many who see your site.

    Reply

  39. I wish to get across my appreciation for your generosity giving support to those who really want help with this one area of interest. Your very own commitment to getting the solution all-around had been extremely powerful and has really empowered others much like me to arrive at their endeavors. Your amazing valuable tutorial entails a lot to me and even further to my office colleagues. Thank you; from all of us.

    Reply

  40. I intended to draft you this bit of word to help say thanks once again on the pleasant basics you have shown on this site. It is really unbelievably generous of you to allow unhampered all that a few individuals might have supplied as an e book to help with making some dough for their own end, especially given that you could possibly have done it in case you considered necessary. Those things in addition acted to be a fantastic way to be certain that someone else have the same passion the same as mine to realize way more related to this matter. I am certain there are several more pleasurable situations ahead for people who check out your website.

    Reply

  42. I would like to voice my respect for your kind-heartedness supporting visitors who actually need assistance with this question. Your real dedication to getting the solution all over appears to be astonishingly beneficial and has all the time made individuals just like me to reach their targets. Your new warm and helpful guideline signifies a whole lot to me and substantially more to my mates. Best wishes; from everyone of us.

    Reply

  44. I simply wished to appreciate you again. I am not sure the things that I would have created without these basics discussed by you over such field. It was actually an absolute horrifying matter for me personally, however , being able to see a new specialized tactic you resolved the issue took me to weep for delight. Now i am happier for your guidance as well as sincerely hope you really know what a powerful job you’re carrying out training the mediocre ones by way of a site. Probably you’ve never encountered all of us.

    Reply

  47. My wife and i got quite fulfilled Michael managed to finish up his studies using the ideas he made in your site. It’s not at all simplistic to just continually be making a gift of guidance other people may have been trying to sell. And we take into account we now have the writer to be grateful to because of that. These illustrations you have made, the simple site menu, the relationships you aid to engender – it’s got many fabulous, and it’s letting our son and our family feel that that topic is thrilling, and that’s pretty fundamental. Thank you for the whole lot!

    Reply

  48. I want to voice my respect for your kindness in support of folks that must have guidance on this one study. Your special dedication to getting the message all through ended up being astonishingly functional and has empowered women just like me to reach their dreams. The useful information signifies this much to me and especially to my office colleagues. Thanks a lot; from each one of us.

    Reply

  49. Can I just say what a aid to seek out someone who actually knows what theyre talking about on the internet. You definitely know the right way to carry a problem to light and make it important. Extra individuals need to learn this and understand this aspect of the story. I cant imagine youre not more standard since you definitely have the gift.

    Reply

  53. Can I just say what a relief to find someone who actually knows what theyre talking about on the internet. You undoubtedly know how you can bring a difficulty to gentle and make it important. Extra people need to learn this and perceive this side of the story. I cant believe youre no more standard since you definitely have the gift.

    Reply

  54. Can I simply say what a aid to search out someone who actually knows what theyre speaking about on the internet. You definitely know easy methods to deliver a problem to gentle and make it important. Extra people have to read this and understand this side of the story. I cant consider youre no more popular since you positively have the gift.

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *

[Programming Problem] Subsets II
Read More
[Programming Problem] Flatten Binary Tree to Linked List
Read More
[Programming Problem] Largest Number
Read More