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.

Example:

Input: n = 3, k = 2
Output: 6
Explanation: Take c1 as color 1, c2 as color 2. All possible ways are:

            post1  post2  post3      
 -----      -----  -----  -----       
   1         c1     c1     c2 
   2         c1     c2     c1 
   3         c1     c2     c2 
   4         c2     c1     c1  
   5         c2     c1     c2
   6         c2     c2     c1

这道题让我们粉刷篱笆，有n个部分需要刷，有k种颜色的油漆，规定了不能有超过连续两根柱子是一个颜色，也就意味着第三根柱子要么根第一个柱子不是一个颜色，要么跟第二根柱子不是一个颜色，问总共有多少种刷法。那么首先来分析一下，如果 n=0 的话，说明没有需要刷的部分，直接返回0即可，如果n为1的话，那么有几种颜色，就有几种刷法，所以应该返回k，当 n=2 时， k=2 时，可以分两种情况来统计，一种是相邻部分没有相同的，一种相同部分有相同的颜色，那么对于没有相同的，对于第一个格子，有k种填法，对于下一个相邻的格子，由于不能相同，所以只有 k-1 种填法。而有相同部分颜色的刷法和上一个格子的不同颜色刷法相同，因为下一格的颜色和之前那个格子颜色刷成一样的即可，最后总共的刷法就是把不同和相同两个刷法加起来，参见代码如下：

解法一：

class Solution {
public:
    int numWays(int n, int k) {
        if (n == 0) return 0;
        int same = 0, diff = k;
        for (int i = 2; i <= n; ++i) {
            int t = diff;
            diff = (same + diff) * (k - 1);
            same = t;
        }
        return same + diff;
    }
};

下面这种解法和上面那方法几乎一样，只不过多了一个变量，参见代码如下：

解法二：

class Solution {
public:
    int numWays(int n, int k) {
        if (n == 0) return 0;
        int same = 0, diff = k, res = same + diff;
        for (int i = 2; i <= n; ++i) {
            same = diff;
            diff = res * (k - 1);
            res = same + diff;
        }
        return res;
    }
};

Github 同步地址：

#276

类似题目：

House Robber II

House Robber

Paint House II

Paint House 

参考资料：

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

https://leetcode.com/problems/paint-fence/discuss/71156/O(n)-time-java-solution-O(1)-space

https://leetcode.com/problems/paint-fence/discuss/178010/The-only-solution-you-need-to-read

LeetCode All in One 题目讲解汇总(持续更新中...)