Paint Fence

Problem Statement

In this problem, you are tasked with painting a linear arrangement of n fence posts using k available colors. The objective is to determine the number of different ways to paint these posts under certain constraints. Each post should be painted with one and only one of the k colors. However, the challenge intensifies with an additional rule: no three consecutive posts can be painted with the same color. The solution should encompass all possible valid ways to paint the fence given any values of n and k.

Examples

Example 1

Input:

n = 3, k = 2

Output:

6

Explanation:

All the possibilities are shown.
Note that painting all the posts red or all the posts green is invalid because there cannot be three posts in a row with the same color.

Example 2

Input:

n = 1, k = 1

Output:

1

Example 3

Input:

n = 7, k = 2

Output:

42

Constraints

• 1 <= n <= 50
• 1 <= k <= 105
• The testcases are generated such that the answer is in the range [0, 231 - 1] for the given n and k.

Approach and Intuition

To devise a way to solve the problem, consider the constraints and the task at hand. We need to find the number of valid combinations of colors while adhering to the rule that no three consecutive posts have the same color.

1. Base Cases Analysis:

   • When n = 1, the process is straightforward, as any post can be painted with any of the k colors, so there are k ways.
   • Extending to n = 2, both posts can independently be any color, providing k * k = k^2 combinations. All combinations are valid here since there’s no possibility of three consecutive posts.

2. Extension to Larger n:

   • For n = 3, expand the possibilities based on the colors of the first two posts. The third post can be any color except the color of the second if the first two are the same. Hence, the problem requires dynamic planning where decisions depend on previous states.
   • Specifically, when constructing combinations for greater than two posts, count the possible end combinations for n-1 and n-2 posts. This leads into a recurrence relation useful for building a dynamic programming solution.

3. Dynamic Programming Approach:

   • Use two arrays or states – same and diff:
     • same[i] represents the number of ways the last two posts of the first i posts have the same color.
     • diff[i] stands for the number of ways the last two of the first i posts have different colors.
   • Transition relations would be:
     • same[i] = diff[i-1]
     • diff[i] = (same[i-1] + diff[i-1]) * (k-1)
     • These relations accommodate that the i-th post can match the previous post (but only if the previous two were different) or differ (where the color can be any of the remaining k-1 choices).
   • Initialize values:
     • same[2] = k
     • diff[2] = k * (k-1)
   • Compute subsequent values using the above transitions up to n.
   • Final configuration count for n posts is same[n] + diff[n].

4. Calculational Example:

   • For n = 3 and k = 2, this results in 6 combinations, as follows from the dynamic programming consideration.

By deciding an approach to enumerate combinations respecting the constraint, it turns a seemingly complex problem into a manageable series of state transitions that reflect the rules of the problem.

Solutions

class Solution {
    public int countWays(int steps, int colors) {
        if (steps == 1) return colors;
        
        int previousTwo = colors;
        int previousOne = colors * colors;
        
        for (int i = 3; i <= steps; i++) {
            int current = (colors - 1) * (previousOne + previousTwo);
            previousTwo = previousOne;
            previousOne = current;
        }
        
        return previousOne;
    }
}

class Solution:
    def countWays(self, steps: int, colors: int) -> int:
        if steps == 1:
            return colors
        
        second_last = colors
        last = colors * colors
        
        for step in range(3, steps + 1):
            current = (colors - 1) * (last + second_last)
            second_last = last
            last = current

        return last