# 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;
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jaywin.gitbook.io/leetcode/solutions/0276-paint-fence.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.