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
- Split the count by whether the current post matches its predecessor:
samecounts arrangements where postiequals posti - 1, anddiffwhere it differs. - Any previous arrangement can be extended with a different colour, giving
diff = (same + diff) * (k - 1). - Post
imay copy posti - 1only if posti - 1differed from posti - 2, which is exactly the previousdiffcount:same = diff_old. - The answer is
same + diff, with the base casessame = 0,diff = kfor 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
sameas 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 == 1base case: a single post can use any of thekcolours. - 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.