In depth visual tutorial on Paint Fence

  • 0

    If you are like me, you need to gain an understanding of the solution, before seeing the solution. This video is 15 minutes long, but if you are completely lost, or lacking in understanding a few parts, this video will hopefully help fill in those blanks. It goes over the Dynamic Programming Solution to Paint Fence, with very very detailed explanations and visuals.

  • 0

    Just to summarize the video for those trying to get a quick understanding.

    1. To color the first post you have k colors to choose from.

    2. To color the second post, you have two options, that is, to make the colors the same or make them different.

    Option A) To make the colors the same, you only have 1 choice, which is to use the same color you choice before. So, that's k choices for the first, and 1 choice for the second, so k*1, or just k.

    Option B)To make the colors different, you have k-1 choices, because you have already chosen 1 color, and the second color can be any color except the first color you chose. So thats k choices for the first color, and k-1 choices for the second, so k * (k-1).

    Finally, for all the rest, you again have two options for each additional posts you need to color, and the answer is based on what was previously chosen.

    Option A) Color the next post the same. The next post can be the same, only if the previous two were different, otherwise you'd have 3 the same in a row, which is a violation. So the number of ways for the post to be the same for 3 or more posts, is if the previous two were different. So (#waystomakepreviousdiff * 1). You multiply by 1 because you are making the post the same, which means you only have 1 color to choose from.

    Option B) Make the post a different color. To make the 3rd or higher post different, the previous post could have been the same or different, but whatever the last choice was, you just have to make it different, which means you elimate the previous color. So for this option we have (same + different) * (k-1).

    A picture is worth a thousand words, so if any of the above is hard to follow, be sure to watch the video:

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.