Solution Explanation: Painting a Fence

This problem involves finding the number of ways to paint a fence of n posts with k colors, ensuring no three or more consecutive posts have the same color. We can solve this efficiently using dynamic programming.

Approach: Dynamic Programming

The core idea is to break down the problem into smaller subproblems. We define two dynamic programming arrays (or variables in the optimized solution):

• f[i] (or f): Represents the number of ways to paint the fence up to post i such that posts i-1 and i have different colors.
• g[i] (or g): Represents the number of ways to paint the fence up to post i such that posts i-1 and i have the same color.

Base Cases:

• f[0] = k (There are k ways to paint the first post).
• g[0] = 0 (There's no way to have two consecutive posts with the same color when there's only one post).

Recursive Relations:

For i > 0:

• f[i] = (f[i-1] + g[i-1]) * (k - 1): To have different colors for posts i-1 and i, we can either extend a configuration where i-1 and i-2 have different colors (f[i-1]) or one where i-1 and i-2 have the same color (g[i-1]). In each case, we have k - 1 choices for the color of post i (it cannot be the same as post i-1).
• g[i] = f[i-1]: To have the same color for posts i-1 and i, we must have had different colors for i-2 and i-1 (f[i-1]).

Final Answer: The total number of ways to paint the fence is f[n-1] + g[n-1]. This sums the configurations where the last two posts have different or the same colors.

Code Examples and Time/Space Complexity

The code examples below demonstrate both the original dynamic programming approach (using arrays) and the space-optimized version (using only two variables).

Time Complexity: O(n) - The algorithms iterate through the posts once.

Space Complexity:

• Original DP: O(n) - We use arrays f and g of size n.
• Optimized DP: O(1) - We use only two variables, f and g.

Python (Original DP)

def numWays(n, k):
    if n == 0: return 0
    f = [0] * n
    g = [0] * n
    f[0] = k
    for i in range(1, n):
        f[i] = (f[i-1] + g[i-1]) * (k - 1)
        g[i] = f[i-1]
    return f[n-1] + g[n-1]

Python (Optimized DP)

def numWays(n, k):
    if n == 0: return 0
    f, g = k, 0  # Initialize f and g
    for _ in range(1, n):
        f, g = (f + g) * (k - 1), f  #Simultaneous update
    return f + g
 

(Similar code structures apply to Java, C++, Go, and TypeScript—the core logic remains the same. The optimized version is generally preferred for its space efficiency.)