Paint Fence — LeetCode 276 Python Solution
MediumLeetCode PremiumDynamic Programming
- Problem
- #276
- Pattern
- 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
Python
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
| Measure | Complexity |
|---|---|
| Time | O(n) |
| Space | O(n), where n is the number of fence posts auxiliary |
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
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.