> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/dynamic_programming_i/duo-zhuang-tai-dp/paint-fence.md).

# Paint Fence

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

> There is a fence with n posts, each post can be painted with one of the k colors.
>
> You have to paint all the posts such that no more than two adjacent fence posts have the same color.
>
> Return the total number of ways you can paint the fence.
>
> Note:
>
> n and k are non-negative integers.

## Thoughts

<https://discuss.leetcode.com/topic/23426/o-n-time-java-solution-o-1-space/2?page=1>

看到问多少种先想到DP. 到第i个post一共能有多少种方法取决于它和前面是不是同一种颜色. 因此想到要用两种状态.\
sameCount表示到i时, 它与前面是同一种颜色, 一共能有多少种; diffCount表示它与前面不同时能有多少种. 由于最多只能有两个连着的相同, 因此sameCount的值等于上一块diffCount的值.

## Code

```
class Solution {
public:
    int numWays(int n, int k) {
        if (n == 0) return 0;
        if (n == 1) return k;
        int same_cnt = k, diff_cnt = k * (k - 1);
        for (int i = 3; i <= n; ++i) {
            int tmp = diff_cnt;
            diff_cnt = (same_cnt + diff_cnt) * (k - 1);
            same_cnt = tmp;
        }
        return same_cnt + diff_cnt;
    }
};
```

```
class Solution {
    public int numWays(int n, int k) {
        if (n == 0) {
            return 0;
        } else if (n == 1) {
            return k;
        }
        int diffCount = k * (k - 1);
        int sameCount = k;
        for (int i = 3; i <= n; i++) {
            int tmp = diffCount;
            diffCount = diffCount * (k - 1) + sameCount * (k - 1);
            sameCount = tmp;
        }
        return diffCount + sameCount;
    }
}
```

## Analysis

时间复杂度O(N).


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## 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://hao-fu-1.gitbook.io/oj/dynamic_programming_i/duo-zhuang-tai-dp/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.