> 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).