⚡Flashcard Drill➔
NeetCode #663LC-276Medium1-D Dynamic ProgrammingNC Algo100
← Back to All Problems

#663 · #276 · Paint Fence(栅栏涂色)

📌 Problem Statement & Constraints

There are n fence posts and k colours. Paint the posts so that no more than two adjacent posts share the same colour. Return the number of valid colourings. Constraints: 1 <= n <= 50, 1 <= k <= 10^5.

💡 Core Algorithmic Approaches

  1. Split the count by whether the current post matches its predecessor: same counts arrangements where post i equals post i - 1, and diff where it differs.
  2. Any previous arrangement can be extended with a different colour, giving diff = (same + diff) * (k - 1).
  3. Post i may copy post i - 1 only if post i - 1 differed from post i - 2, which is exactly the previous diff count: same = diff_old.
  4. The answer is same + diff, with the base cases same = 0, diff = k for a single post.

💻 Benchmark Python3 Implementation

class Solution:
    def numWays(self, n: int, k: int) -> int:
        if n == 0:
            return 0
        if n == 1:
            return k
        same, diff = 0, k              # for the first post
        for _ in range(2, n + 1):
            same, diff = diff, (same + diff) * (k - 1)
        return same + diff

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one pass over the posts.
💾 Space Complexity
O(1): two scalars.

⚠️ Interview Pitfalls & Follow-ups

  • Defining same as an unconditional copy of the previous post: that would allow three equal posts in a row; the copy must come from a post that differed from its own predecessor.
  • Forgetting the n == 1 base case: a single post can use any of the k colours.
  • Using k * (k - 1)^(n - 1): that enforces no two adjacent posts are equal, which is a stricter (different) rule.
  • Multiplying the same-colour transition by k - 1: copying the previous colour has exactly one choice.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related 1-D Dynamic Programming Problems