Easy

思路不难，但题意一开始不好懂. 而且写起代码来好些地方细节还得注意才行.
首先这道题跟之前house rubber那些题不一样，它是要求不能连续两个以上选相同的颜色. 英语读起来很拗口，意思就是最多两个连续的posts有相同的颜色，三个或三个以上不能. 用int代表color, "1100210"这种就可以，但是“1110021"这种就不行.

用dp做，开两个数组same和diff： same[i]表示第i个post has the same color as 第i - 1个post；diff[i]表示第i个post has different color from第i - 1个post.注意一下前面为什么要单独写出来3项.首先same[0],diff[0]都没有意义，是为了让index跟第几个post对应多开出来的，所以初始化值为0不会改. 但是为什么for 循环要从i = 3开始呢？

关键在于diff[2]:它表示第二个跟第一个栅栏柱要涂不同的颜色，那么我们知道第二个栅栏柱可以涂的颜色有k - 1种，然后我们要去乘以前面所有可能的情况. 因为前面只有第一个栅栏柱，所以我们不能用same[i - 1] + diff[i - 1]这个方法去计算，这样算出来是2k.因为实际上只有total k种方法去染这一个栅栏柱. 这就是i = 2之前特殊的地方. i = 3开始往后，每一次我们更新diff[i]的时候，都可以直接用第i个栅栏柱可以涂的颜色数k - 1去乘以前面所有的染色方案树数，而当i >= 3时这个前面总的染色方案数可以直接用same[i - 1] + diff[i - 1]去计算，因为没有重复计算.

class Solution {
    public int numWays(int n, int k) {
    //no more than two adjacent fence posts have the same color.        
    //011002 allowed
    //000112 not allowed
        if (n == 0 || k == 0){
            return 0;
        }
        if (n == 1){
            return k;
        }
        int[] same = new int[n + 1];
        int[] diff = new int[n + 1];
        //same[i] : the ith post has the same color as the i-1 th post
        //diff[i] : the ith post has different color from the i-1 th post
        same[1] = k;
        same[2] = k;
        diff[1] = k;
        diff[2] = k*(k - 1);
        for (int i = 3; i < n + 1; i++){
            same[i] = diff[i - 1];
            diff[i] = (same[i - 1] + diff[i - 1]) * (k - 1);
        }    
        return same[n] + diff[n]; 
    }
}

通常来说Easy的dp问题最优化都得空间O(1), 按照上面那个思路做就可以了. 会House rubbery O(1) space的做法就会这道题的.

class Solution {
    public int numWays(int n, int k) {
        if (n == 0 || k == 0){
            return 0;
        }
        if (n == 1){
            return k;
        }
        //calculate the total ways to paint the first two fence posts
        int same = k;
        int diff = k*(k - 1);
        int temp = 0;
        for (int i = 2; i < n; i++){
            temp = diff; 
            diff = (same + diff) * (k - 1); 
            same = temp; 
        }
        return same + diff;
    }
}