Problem Description

The "Paint Fence" problem asks: Given n fence posts and k different colors, in how many ways can you paint all the posts such that no more than two adjacent fence posts have the same color?

Key constraints:

• Each post must be painted with one of the k colors.
• No more than two adjacent posts can have the same color (i.e., you cannot have three or more posts in a row with the same color).
• Return the total number of valid ways to paint the fence.
• Typically, n and k are positive integers (n ≥ 1, k ≥ 1).

Thought Process

At first glance, it might seem like we can simply choose any color for each post, yielding k^n combinations. However, the constraint that no more than two adjacent posts can have the same color complicates things.

A brute-force approach would consider every possible painting and check if it meets the constraint, but this is highly inefficient for large n or k.

To optimize, we can use dynamic programming by recognizing that the color of the current post depends on the colors of the previous one or two posts. This allows us to build up the solution efficiently by keeping track of valid combinations as we paint each post.

Solution Approach

We'll use dynamic programming to solve this problem efficiently. Let's define:

• same: The number of ways to paint the current post the same color as the previous post.
• diff: The number of ways to paint the current post a different color than the previous post.

1. For the first post, we have k options.
2. For the second post:
   • same: The second post can only be the same color as the first if we pick one of the k colors for the first, and then use the same color again. So there are k ways.
   • diff: The second post can be any of the k-1 other colors. So, k * (k-1) ways.
3. For posts 3 to n:
   • If we paint the current post the same as the previous one (same), then the previous two must have been different (diff).
     same = diff_prev * 1
   • If we paint the current post a different color (diff), then the previous post could have been painted in any valid way, and we choose any of the k-1 colors.
     diff = (same_prev + diff_prev) * (k-1)
4. The total number of ways to paint the fence is same + diff after the last post.

We use just two variables to keep track of previous computations, optimizing space to O(1).

Example Walkthrough

Example: n = 3, k = 2

1. First post: k = 2 ways (either color A or color B).
2. Second post:
   • same = 2 (paint same as first post)
   • diff = 2 (paint different from first post)
3. Third post:
   • same = diff_prev = 2 (can only be same as previous if previous two were different)
   • diff = (same_prev + diff_prev) * (k-1) = (2 + 2) * 1 = 4
4. Total ways = same + diff = 2 + 4 = 6

All possible combinations for 3 posts and 2 colors, ensuring no three adjacent are the same, are accounted for.

Time and Space Complexity

Brute-force approach:

• Time: O(k^n), since each post can be painted in k ways, and we check all combinations.
• Space: O(n), for the recursion stack or to store each combination.

• Time: O(n), since we process each post exactly once.
• Space: O(1), since we only track two variables (same and diff) at each step.

The dynamic programming approach is much more efficient and scalable for large n and k.

Summary

The Paint Fence problem is a classic example of how dynamic programming can simplify combinatorial problems with constraints. By recognizing the relationship between the current and previous posts, we can avoid redundant calculations and achieve a linear-time solution. The key insight is to track scenarios where the last two posts are the same or different, enabling us to efficiently compute the total number of valid colorings. This approach is both elegant and highly efficient compared to brute-force enumeration.

Code Implementation

def numWays(n, k):
    if n == 0:
        return 0
    if n == 1:
        return k
    same = k * 1
    diff = k * (k - 1)
    for i in range(3, n + 1):
        prev_diff = diff
        diff = (same + diff) * (k - 1)
        same = prev_diff * 1
    return same + diff
      

class Solution {
public:
    int numWays(int n, int k) {
        if (n == 0) return 0;
        if (n == 1) return k;
        int same = k * 1;
        int diff = k * (k - 1);
        for (int i = 3; i <= n; ++i) {
            int prev_diff = diff;
            diff = (same + diff) * (k - 1);
            same = prev_diff * 1;
        }
        return same + diff;
    }
};
      

class Solution {
    public int numWays(int n, int k) {
        if (n == 0) return 0;
        if (n == 1) return k;
        int same = k * 1;
        int diff = k * (k - 1);
        for (int i = 3; i <= n; i++) {
            int prev_diff = diff;
            diff = (same + diff) * (k - 1);
            same = prev_diff * 1;
        }
        return same + diff;
    }
}
      

var numWays = function(n, k) {
    if (n === 0) return 0;
    if (n === 1) return k;
    let same = k * 1;
    let diff = k * (k - 1);
    for (let i = 3; i <= n; i++) {
        let prev_diff = diff;
        diff = (same + diff) * (k - 1);
        same = prev_diff * 1;
    }
    return same + diff;
};