LeetCode 276: Paint Fence - All Solutions Explained

Problem Statement

The Paint Fence problem (LeetCode 276) is a medium-level dynamic programming challenge. Given n fence posts and k different colors, determine the number of ways to paint all the fences such that no more than two adjacent fences have the same color.

Copy codeInput: n = 3, k = 2
Output: 6
Explanation:
All possible colorings:
1. post1=red, post2=red, post3=blue
2. post1=red, post2=blue, post3=red
3. post1=red, post2=blue, post3=blue
4. post1=blue, post2=blue, post3=red
5. post1=blue, post2=red, post3=blue
6. post1=blue, post2=red, post3=red

Explanation of the Best Solution

This approach uses dynamic programming to track valid painting combinations:

1. Base Cases:
2. For 1 fence: k ways

3. For 2 fences: k × k ways

4. DP Relation:

5. same[i] = diff[i-1] (can only match if previous was different)
6. diff[i] = (same[i-1] + diff[i-1]) × (k-1) (any color except previous)

7. Total ways: same[n] + diff[n]

8. Space Optimization:

9. Only need to track previous states, not entire array

Step-by-Step Example

For n=3, k=2: 1. same[1] = 0, diff[1] = 2 2. same[2] = 2, diff[2] = 2 3. same[3] = 2, diff[3] = (2+2)×1 = 4 4. Total = 2 + 4 = 6

Python Code (DP Solution)

Copy codeclass Solution:
    def numWays(self, n: int, k: int) -> int:
        if n == 0:
            return 0
        if n == 1:
            return k

        same, diff = k, k * (k - 1)

        for i in range(3, n + 1):
            same, diff = diff, (same + diff) * (k - 1)

        return same + diff

# Test case
print(Solution().numWays(3, 2))  # Output: 6

Complexity

• Time Complexity: O(n) - Single pass through fence posts
• Space Complexity: O(1) - Constant space with optimization
• Optimizations: Only stores previous two states

Why It's the Best

• Optimal O(n) time complexity
• Minimal space requirements
• Clear mathematical formulation
• Standard approach for counting problems with constraints

Solution 2: Recursion with Memoization (Alternative)

Explanation

This recursive approach with memoization demonstrates the problem's structure:

1. Base Cases:
2. 0 fences: 0 ways
3. 1 fence: k ways

4. 2 fences: k × k ways

5. Recursive Relation:

6. If previous two same: (k-1) × f(n-1)
7. If previous two different: (k-1) × f(n-1) + f(n-2)
8. Memoization: Store computed results to avoid recomputation

Python Code (Memoization Solution)

Copy codeclass Solution:
    def numWays(self, n: int, k: int) -> int:
        memo = {}

        def dp(i):
            if i == 0:
                return 0
            if i == 1:
                return k
            if i == 2:
                return k * k
            if i in memo:
                return memo[i]

            memo[i] = (k - 1) * (dp(i - 1) + dp(i - 2))
            return memo[i]

        return dp(n)

# Test case
print(Solution().numWays(3, 2))  # Output: 6

Complexity

• Time Complexity: O(n) - With memoization
• Space Complexity: O(n) - For recursion stack and memo storage
• Drawbacks: Recursion overhead

Pros and Cons

• Pros: Clearly shows recursive structure
• Cons: Less efficient than iterative DP
• Best for: Understanding problem's recursive nature

Edge Cases to Consider

• n = 0 → 0 ways
• n = 1 → k ways
• k = 1 and n > 2 → 0 ways (can't satisfy constraint)
• Large n (50) and large k (10⁵) → verify integer limits
• All possible color combinations → correctness test

Final Thoughts

• DP Solution: Best for most cases (optimal performance)
• Memoization: Good for understanding recursive structure
• Key Insight: Separate same/different color cases
• Advanced Consideration: Can be modeled as a state machine

For further practice, try similar problems like Climbing Stairs (LeetCode 70) or House Robber (LeetCode 198).