MediumNo. 0276LeetCode Premium
Paint Fence — LeetCode 276 Python Solution
- Pattern
- Dynamic Programming
- Topics
- Dynamic Programming
- Reading time
- 2 min
- Source
- leetcode.com
The problem
You are painting a fence of n posts with k different colors. You must paint the posts following these rules: Every post must be painted exactly one color.
Example
- Input
- n = 3, k = 2
- Output
- 6
- Explanation
- All the possibilities are shown.
Python solution
class Solution:
def numWays(self, n: int, k: int) -> int:
f = [0] * n
g = [0] * n
f[0] = k
for i in range(1, n):
f[i] = (f[i - 1] + g[i - 1]) * (k - 1)
g[i] = f[i - 1]
return f[-1] + g[-1]Complexity
- Time
- O(n)
- Space · auxiliary
- O(n)where n is the number of fence posts
Pattern: Dynamic Programming
Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 276. Paint Fence is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Dynamic Programming.
The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0279 | Perfect Squares | Medium |
| 0010 | Regular Expression Matching | Hard |
| 0022 | Generate Parentheses | Medium |
| 0032 | Longest Valid Parentheses | Hard |
| 0044 | Wildcard Matching | Hard |
| 0045 | Jump Game II | Medium |
Frequently asked questions
- How hard is LeetCode 276. Paint Fence?
LeetCode 276. Paint Fence is rated Medium on LeetCode.
- What is the time complexity of LeetCode 276. Paint Fence?
The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 276. Paint Fence?
The Python solution on this page uses O(n), where n is the number of fence posts auxiliary space.
- What topics does LeetCode 276. Paint Fence cover?
LeetCode 276. Paint Fence is tagged Dynamic Programming on LeetCode.
- Is LeetCode 276. Paint Fence a premium problem?
Yes. LeetCode 276. Paint Fence is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.