> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/solutions/0276-paint-fence.md).

# 0276. Paint Fence

<https://leetcode.com/problems/paint-fence>

## Description

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.
* There **cannot** be three or more **consecutive** posts with the same color.

Given the two integers `n` and `k`, return *the **number of ways** you can paint the fence*.

**Example 1:**

![](https://assets.leetcode.com/uploads/2021/02/28/paintfenceex1.png)

```
**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 <= 50`
* `1 <= k <= 105`
* The testcases are generated such that the answer is in the range `[0, 231 - 1]` for the given `n` and `k`.

## ac

```java
class Solution {
    public int numWays(int n, int k) {
        // edge cases
        if (n <= 0 || k <= 0) return 0;
        if (n == 1) return k;

        // dp
        int same = k;
        int diff = k * (k - 1);
        for (int i = 2; i < n; i++) {
            int tmp = diff;
            diff = (same + diff) * (k - 1);
            same = tmp;
        }

        return diff + same;
    }
}
```