Google Interview - 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.

因为题目要求是不超过两个相邻的栅栏有同样颜色，所以可以把题目分解一下：
设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

其实可以有更简单的方法，涂到第 n 个的可能总数为 ① 与 n-1 时的不同可能数，即(k-1)*T(n-1)；加上 ② 与 n-1 时的相同可能数，因为连续相同不能超过两个，第 n 和 n-1 个的颜色和第 n-2 个肯定不同，所以与 n-1 时的相同数必定等于 n-2 时的不同可能数，即(k-1)*T(n-2) ，于是有：

T(n) = (k - 1) * (T(n-1) + T(n-2)), n > 2 

 

int num_colors(int n, int k) {
    if(n<=0 || k<=0) return 0;
    vector<int> f = {0, k, k*k};
    f.resize(n+1);
    for(int i=3; i<=n; i++) {
        f[i] = (k-1) * (f[i-1] + f[i-2]);
    }
    return f[n];
}