NUHMAN.com

Introduction

LeetCode 276: Paint Fence is a classic dynamic programming problem. You're given n posts and k colors, and you must determine how many ways you can paint the fence such that no more than two adjacent posts have the same color.

This is a perfect example of solving a problem with constraints by using state transition logic and reducing overlapping subproblems with DP.

Problem Statement

You are painting a fence of n posts with k colors. You must not paint more than two adjacent posts with the same color.

Return the total number of ways to paint the fence.

Examples

python

Input: n = 3, k = 2
Output: 6

Explanation:
- Ways: [1,1,2], [1,2,1], [2,2,1], [2,1,1], [1,2,2], [2,1,2]

✅ Step-by-Step Breakdown

🔑 Key Constraints

• You can paint two adjacent posts the same color.
• You cannot paint three or more adjacent posts the same color.

🧠 Dynamic Programming Strategy

We define:

• same: number of ways where last two posts are the same color
• diff: number of ways where last two posts are different colors

🧮 Base Cases

• n == 0: return 0 (no fence, no painting)
• n == 1: return k (each post can be painted in k ways)

🔄 Recurrence Relations

From the second post onward:

• same[i] = diff[i-1] * 1 → Only one way to continue same color
• diff[i] = (same[i-1] + diff[i-1]) * (k - 1) → Pick a different color from previous

✅ Python Code

python

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

        same = 0
        diff = k

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

        return same + diff

🧪 Dry Run

For n = 3, k = 2:

1. i = 2:

• same = 2 (prev diff)
• diff = (2 + 0) * 1 = 2

1. i = 3:

• same = 2
• diff = (2 + 2) * 1 = 4

Result: 2 + 4 = 6

⏱️ Time and Space Complexity

MetricValueTime ComplexityO(n)Space ComplexityO(1)

🔍 Edge Cases

• n = 0 → 0
• k = 1 and n > 2 → Invalid (only one color, three adjacent not allowed)
• k >= n → Usually valid with many combinations

✅ Conclusion

LeetCode 276: Paint Fence is a smart exercise in:

• Managing state transitions (same, diff)
• Building clean and space-efficient dynamic programming solutions