1. Top-Down Dynamic Programming (Recursion + Memoization)

Intuition

The constraint is that no more than two consecutive posts can have the same color. For each post, we can either paint it a different color from the previous post, or paint it the same color (but only if the two previous posts are different).

This leads to a recurrence: totalWays(i) = (k - 1) * (totalWays(i - 1) + totalWays(i - 2)). The first term handles painting post i differently from post i - 1 (k - 1 choices). The second term handles painting post i the same as post i - 1, which requires post i - 1 to be different from post i - 2.

Algorithm

1. Define totalWays(i) to return the number of valid ways to paint posts 1 through i.
2. Base cases: totalWays(1) = k and totalWays(2) = k * k.
3. For i > 2, use the recurrence: totalWays(i) = (k - 1) * (totalWays(i - 1) + totalWays(i - 2)).
4. Use memoization to cache results and avoid redundant computation.
5. Return totalWays(n).

class Solution:
    def numWays(self, n: int, k: int) -> int:
        def total_ways(i):
            if i == 1:
                return k
            if i == 2:
                return k * k
            
            # Check if we have already calculated totalWays(i)
            if i in memo:
                return memo[i]
            
            # Use the recurrence relation to calculate total_ways(i)
            memo[i] = (k - 1) * (total_ways(i - 1) + total_ways(i - 2))
            return memo[i]

        memo = {}
        return total_ways(n)

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$

Where $n$ is the number of fence posts.

---

2. Bottom-Up Dynamic Programming (Tabulation)

Intuition

The same recurrence can be computed iteratively instead of recursively. We fill an array from the base cases up to n, which avoids recursion overhead and stack depth issues.

This approach is often more efficient in practice since it avoids function call overhead and naturally iterates through states in order.

Algorithm

1. Handle base cases: if n is 1, return k. If n is 2, return k * k.
2. Create an array totalWays of size n + 1.
3. Set totalWays[1] = k and totalWays[2] = k * k.
4. For i from 3 to n, compute totalWays[i] = (k - 1) * (totalWays[i - 1] + totalWays[i - 2]).
5. Return totalWays[n].

class Solution:
    def numWays(self, n: int, k: int) -> int:
        # Base cases for the problem to avoid index out of bound issues
        if n == 1:
            return k
        if n == 2:
            return k * k

        total_ways = [0] * (n + 1)
        total_ways[1] = k
        total_ways[2] = k * k
        
        for i in range(3, n + 1):
            total_ways[i] = (k - 1) * (total_ways[i - 1] + total_ways[i - 2])
        
        return total_ways[n]

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$

Where $n$ is the number of fence posts.

---

3. Bottom-Up, Constant Space

Intuition

Since the recurrence only depends on the previous two values, we do not need to store the entire array. We can use two variables to track totalWays(i - 1) and totalWays(i - 2), updating them as we iterate.

This optimization reduces space complexity from O(n) to O(1).

Algorithm

1. If n is 1, return k.
2. Initialize twoPostsBack = k and onePostBack = k * k.
3. For i from 3 to n:
   • Compute curr = (k - 1) * (onePostBack + twoPostsBack).
   • Shift: twoPostsBack = onePostBack, onePostBack = curr.
4. Return onePostBack.

class Solution:
    def numWays(self, n: int, k: int) -> int:
        if n == 1:
            return k
        
        two_posts_back = k
        one_post_back = k * k
        
        for i in range(3, n + 1):
            curr = (k - 1) * (one_post_back + two_posts_back)
            two_posts_back = one_post_back
            one_post_back = curr

        return one_post_back

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(1)$ constant space

Where $n$ is the number of fence posts.

---

Common Pitfalls

Misunderstanding the Three Consecutive Constraint

The problem forbids more than two consecutive posts with the same color. Some solvers mistakenly interpret this as no two adjacent posts can share a color, which is too restrictive. Two adjacent posts can have the same color as long as there is not a third consecutive post with that same color.

Incorrect Base Cases for Small n

When n equals 1, there are exactly k ways. When n equals 2, there are k*k ways since any combination is valid (no three consecutive posts exist yet). Forgetting to handle these base cases or computing them incorrectly leads to wrong answers and potential index-out-of-bounds errors.

Deriving the Wrong Recurrence Relation

The recurrence totalWays(i) = (k-1) * (totalWays(i-1) + totalWays(i-2)) accounts for two scenarios: painting differently from the previous post, or painting the same as the previous post (which requires the two before that to be different). Confusing the logic of when same-color painting is allowed leads to an incorrect formula.