Problem

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.

Example

Given n=3, k=2 return 6

      post 1,   post 2, post 3
way1    0         0       1 
way2    0         1       0
way3    0         1       1
way4    1         0       0
way5    1         0       1
way6    1         1       0

Note

DP的做法是，先分析最优解的结构特征，写出dp数组的初值以及递推表达式，然后从前向后循环，递归记录每一步的最优解。
这道题就是一个最优解问题，很明显应该采用动规。dp[i]是涂到第i个fence时方法的总数，只和前两个fence的颜色方案有关。以三个栅栏为例，栅栏1有k种颜色可选，栅栏2亦然，栅栏3则要看前两个栅栏，1和2的颜色是否相同。如果3和2可以相同，那么必定和1不同，这种情况3有k-1种方案；如果3和2不可以相同，那么说明1和2相同，所以3也只有k-1种方案。

Solution

public class Solution {
    public int numWays(int n, int k) {
        int[] dp = new int[n];
        if (n == 0) return 0;
        if (n == 1) return k;
        dp[0] = k;
        dp[1] = k*k;
        for (int i = 2; i < n; i++) {
            dp[i] = (k-1)*(dp[i-1]+dp[i-2]);
        }
        return dp[n-1];
    }
}

O(1) Space DP

public class Solution {
   public int numWays(int n, int k) {
        if (n == 0 || k == 0) return 0;
        if (n == 1) return k;
        int lastTwo = k;
        int lastOne = k*k;
        for (int i = 2; i < n; i++) {
            int curOne = lastOne * (k-1) + lastTwo * (k-1);
            lastTwo = lastOne;
            lastOne = curOne;
        }
        return lastOne;
    }
}