You are painting a fence of n posts with k different colors. You must paint the posts following these rules:
Given the two integers n and k, return the number of ways you can paint the fence.
Example 1:
Input: n = 3, k = 2 Output: 6 Explanation: All the possibilities are shown. Note that painting all the posts red or all the posts green is invalid because there cannot be three posts in a row with the same color.
Example 2:
Input: n = 1, k = 1 Output: 1
Example 3:
Input: n = 7, k = 2 Output: 42
Constraints:
1 <= n <= 501 <= k <= 105[0, 231 - 1] for the given n and k.Problem Overview: You are given n fence posts and k paint colors. Each post must be painted one color, but no more than two adjacent posts can share the same color. The task is to compute how many valid painting combinations exist.
Approach 1: Dynamic Programming (O(n) time, O(n) space)
This problem fits naturally into dynamic programming because the number of valid ways for the current post depends on previous posts. Track two states for each position: same[i] (ways where post i has the same color as i-1) and diff[i] (ways where post i has a different color). If the current post uses the same color, the previous pair must have been different to avoid three consecutive matches. That gives same[i] = diff[i-1]. For different colors, you can pick any of the remaining k-1 colors regardless of the previous pair: diff[i] = (same[i-1] + diff[i-1]) * (k - 1). Iterate from post 3 to n while updating these states. The final answer is same[n] + diff[n]. This approach runs in O(n) time and uses O(n) space for the DP arrays.
The key insight is recognizing that the constraint only depends on the last two posts. Instead of tracking full color sequences, you only track whether the last two colors match or differ. This dramatically reduces the state space while keeping transitions simple.
Approach 2: Dynamic Programming (Space Optimization) (O(n) time, O(1) space)
The DP arrays are unnecessary because each state depends only on the previous step. Maintain two variables: same and diff. Initialize for the first two posts: same = k (both posts same color) and diff = k * (k - 1) (two different colors). For every additional post, compute newSame = diff and newDiff = (same + diff) * (k - 1). Update the variables and continue iterating until post n. The final count is same + diff. This keeps the time complexity at O(n) while reducing memory to O(1).
This optimization is common in dynamic programming problems where each state depends only on the previous iteration. The transition logic remains identical; only the storage strategy changes.
Recommended for interviews: Interviewers typically expect the dynamic programming insight that tracks same and diff states. Implementing the O(1) space version shows strong understanding of state transitions and memory optimization. The array-based DP version still demonstrates the correct recurrence and reasoning, but the constant-space variant is the polished solution most candidates present in interviews involving dynamic programming.
We define f[i] to represent the number of ways to paint the fence posts from [0..i] such that the last two posts have different colors, and g[i] to represent the number of ways to paint the fence posts from [0..i] such that the last two posts have the same color. Initially, f[0] = k and g[0] = 0.
When i > 0, we have the following state transition equations:
$
\begin{aligned}
f[i] & = (f[i - 1] + g[i - 1]) times (k - 1) \
g[i] & = f[i - 1]
\end{aligned}
The final answer is f[n - 1] + g[n - 1].
The time complexity is O(n) and the space complexity is O(n), where n$ is the number of fence posts.
Python
Java
C++
Go
TypeScript
We notice that f[i] and g[i] are only related to f[i - 1] and g[i - 1]. Therefore, we can use two variables f and g to record the values of f[i - 1] and g[i - 1] respectively, thus optimizing the space complexity to O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Dynamic Programming | — |
| Dynamic Programming (Space Optimization) | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming (same/diff arrays) | O(n) | O(n) | Good for learning the recurrence and visualizing DP state transitions |
| Dynamic Programming (Space Optimized) | O(n) | O(1) | Preferred solution in interviews or memory-constrained scenarios |
Paint Fence (Leetcode) Dynamic Programming | Explanation with Code • Pepcoding • 56,521 views views
Watch 9 more video solutions →Practice Paint Fence with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor