276. Paint Fence

Problem Description

You are tasked with painting a fence that has n posts using k different colors. The challenge is to abide by two main rules while painting:

1. Each fence post must be painted with exactly one color.
2. You are not allowed to paint three or more consecutive fence posts with the same color.

The problem requires you to calculate the total number of different ways you can paint the fence adhering to the above rules. n represents the total number of posts and k represents the number of colors you have at your disposal.

Intuition

The solution to this problem can be approached using dynamic programming because the way you paint the current post is dependent on how you painted the previous ones. The key insight is that the number of ways to paint the last post depends on the color of the second to last post.

Let's define two scenarios:

1. The last two posts have the same color.
2. The last two posts have different colors.

Given that we cannot paint three consecutive posts with the same color, if the last two posts are of the same color, the current post can only be painted with any of the k-1 remaining colors. If the last two posts have different colors, then the current post can also be painted with any of the k-1 remaining colors. However, network need to consider different ways to reach these scenarios.

Thus, we define a dynamic programming table dp where dp[i][0] represents the number of ways to paint up to post i where the last two posts are of different colors, and dp[i][1] represents the number of ways where the last two posts are the same.

The recurrence relations based on the defined scenarios are as follows:

• dp[i][0] (different colors) = (dp[i - 1][0] + dp[i - 1][1]) * (k - 1)
• dp[i][1] (same colors) = dp[i - 1][0]

The reason behind these relations is that, for dp[i][0], you have both previous scenarios possible and you cannot use the last color used, hence k - 1 options. For dp[i][1], you can only come from the scenario where previous colors are different, and you must use the same color as the last one, hence only one option available.

The initial conditions are:

• dp[0][0] = k (because the first post can be any of the k colors)
• dp[0][1] is not applicable because there is no previous post

We iterate through the posts, calculating the number of ways based on the above recurrence relations. Finally, the answer is the sum of ways for the last post being either the same or different colors as the one before it, i.e., sum(dp[-1]).

Learn more about Dynamic Programming patterns.

Solution Approach

The given solution implements the intuition using a dynamic programming (DP) approach. The essential components of this solution are:

1. Data Structure: A 2D list dp with n rows and 2 columns, used to store the number of ways to paint up to the current post. Here, n is the number of fence posts. The first column (dp[i][0]) stores the number of ways if the last two posts have different colors, and the second column (dp[i][1]) stores the number if they are the same.

2. Initialization: The DP table is initialized with dp[0][0] = k, representing the k ways to paint the first fence. Since there is no post before the first one, we don't need to initialize dp[0][1] as it is not applicable.

3. Iteration: The code iterates over each post from 1 to n-1. For each post, the following calculations are performed:

   • dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) * (k - 1): The last two posts can be either different or the same, but the current post must be a different color than the last one, hence (k - 1) choices.
   • dp[i][1] = dp[i - 1][0]: The last two posts must be of different colors for the current post to have the same color as the last one. There is exactly one way to paint it, which is the same color as the previous post.

4. Final Calculation: After filling the DP table up to n posts, the total ways to paint the fence can be found by adding the values of the last row of the DP table: sum(dp[-1]). This is because the final post can either be painted the same or a different color from the one before it, and we are interested in all possible valid combinations.

The core of this algorithm lies in understanding the constraints and how they impact the subsequences and the transitions between states in the dynamic programming table. This solution maintains constant space complexity for each post with respect to the number of colors, making the overall space complexity O(n). The time complexity is O(n) as well because we compute the entries of the DP table with constant time operations for each of the n posts.

The final result is returned by summing the two scenarios in the last row, which provides the count of all the ways to paint the fence according to the rules.

Example Walkthrough

Let's walk through an example to illustrate the solution approach using the given problem and intuition. Suppose we have n = 3 posts to paint and k = 2 different colors. We want to find out how many ways we can paint the fence.

We initialize a DP table dp with dimensions [n][2] where n is the number of fence posts. Each entry dp[i][0] will store ways we can paint up to the i-th post with the last two posts having different colors, and dp[i][1] will store ways with the last two posts having the same color.

Step 1: Initialization

For the first fence post (i = 0), we have k options, assuming k is not zero. So, dp[0][0] = k since there is no previous post, and the condition for dp[0][1] is not applicable.

For k = 2, the initialization would be dp[0][0] = 2 (we have 2 ways to paint the first post as there are 2 colors).

Step 2: Iteration for the second post

Now, let's move to the second post i = 1. We have two scenarios:

• dp[1][0] = (dp[0][0] + dp[0][1]) * (k - 1) since we can paint the second post with a different color than the first in k - 1 ways. Here, dp[0][1] can be considered 0 because it's not applicable. So, dp[1][0] = (2 + 0) * (2 - 1) = 2.
• dp[1][1] = dp[0][0] since the last two posts can be the same if the first post was unique, which is already counted in dp[0][0]. Therefore, dp[1][1] = 2.

At this point, our DP table for i = 1 looks like this:

1dp = [
2  [2, X],  // X denotes non-applicable
3  [2, 2],
4]

Step 3: Iteration for the third post

For the third post i = 2, we follow a similar procedure:

• dp[2][0] = (dp[1][0] + dp[1][1]) * (k - 1) which translates to (2 + 2) * (2 - 1) = 4. We have 4 ways to paint the third post with a different color than the second post.
• dp[2][1] = dp[1][0] since again, the last two can be the same only if the previous two were different. So we take the value from dp[1][0] which is 2, giving us dp[2][1] = 2.

Now, our DP table for i = 2 looks like this:

1dp = [
2  [2, X], 
3  [2, 2],
4  [4, 2],
5]

Step 4: Final Calculation

After computing all the values, we want the sum of the last row to get the total number of ways to paint the fence according to the problem's rules. sum(dp[2]) = dp[2][0] + dp[2][1] = 4 + 2 = 6.

Thus, there are 6 different ways to paint the 3 posts using 2 colors while following the given rules. This completes the example walk-through using the dynamic programming solution approach described in the content.

Solution Implementation

Time and Space Complexity

The given Python code is a dynamic programming solution for a problem where we want to calculate the number of ways to paint a fence with n posts using k colors, such that no more than two adjacent fence posts have the same color.

The time complexity of the code is O(n), where n is the number of fence posts. This is because there is a single for-loop that iterates from 1 to n-1, with each iteration performing a constant number of operations.

The space complexity of the code is also O(n), since it uses a 2D list dp with size n x 2 to store the number of ways to paint the fence for each post, considering whether the current post has the same color as the previous post or not (0 for different, 1 for the same).

Learn more about how to find time and space complexity quickly using problem constraints.