---
title: "276. Paint Fence"
url: "https://laigary.com/interview/coding/276-paint-fence"
type: "note"
section: "coding"
date: "2024-02-14"
updated: "2026-07-27"
tags: ["Dynamic Programming"]
---

# 276. Paint Fence

[276\. Paint Fence](https://leetcode.com/problems/paint-fence/)

```python
class Solution:
    def numWays(self, n: int, k: int) -> int:
        
        @cache
        def dfs(ways):
            if ways == 1:
                return k
            if ways == 2:
                return k * k

            return (k - 1) * (dfs(ways - 1) + dfs(ways - 2))
        
        return dfs(n)
```