[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

27 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

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