Fence Painter

来源：Meequn, fgsdb博客, Google

原帖：http://www.fgdsb.com/2015/01/04/fence-painter/

题目：
Write an algorithm that counts the number of ways you can paint a fence with N posts using K colors such that no more than 2 adjacent fence posts are painted with the same color.

思路：
主要考虑最后两位相同和不同，然后推导dp关系
因为题目要求是不超过两个相邻的栅栏有同样颜色，所以可以把题目分解一下：
设T(n)为符合要求的染色可能总数，S(n)为最后两个相邻元素为相同颜色的染色可能数，D(n)为最后两个相邻元素为不同颜色的染色可能数。显然
D(n) = (k - 1) * (S(n-1) + D(n-1))
S(n) = D(n-1)
T(n) = S(n) + D(n)
带入化简一下得出：
T(n) = (k - 1) * (T(n-1) + T(n-2)), n > 2

代码:

 int numberWays(int n, int k) {   
     if (n == 1) return k;   
     if (n == 2) return k * k;   
     int prev_prev = k, prev = k*k;   
     for (int i = 3; i <= n; ++i) {   
         int old = prev;   
         prev = (k-1)*(prev + prev_prev);   
         prev_prev = old;   
     }   
     return prev;   
 }    
   
 int main() {   
     int k = 2, n = 10;   
     for (int i = 1; i <= n; ++i) {   
         cout << numberWays(i,k) << " ";   
     }   
     cout << endl;   
     return 0;   
 }