https://leetcode.com/problems/paint-fence/description/
image.png
这道题因为不能超过2个连续颜色一样的栅栏。我们想如果每个都需要不一样，
那么N个颜色，就是Nn-1n-1*n-1 。。。就可以了。
现在允许2个一样。我们就需要多一个状态，代表前面是以2种相同颜色结尾的。
所以dp2[i] 就代表到I为止，前面是2种相同颜色的有几种组合。
dp[i] 代表到I为止，前面只有1种相同颜色的有几种组合。
dp2[i] = dp[i-1] ,因为I的位置的染色必须要和I-1一致。
dp[i] = (dp[i-1]+dp2[i-1])*(n-1),可以是和前一位不同的N-1种颜色或者是和前2位颜色一致的方案的不同的N-1种颜色。
public int numWays(int n, int k) {
if(n == 0) return 0;
if(n == 1) return k;
int[] dp = new int[n];
dp[0] = k;
dp[1] = k*(k-1);
int[] dp2 = new int[n];
dp2[1] = k;
for(int i = 2; i < n; i++){
dp2[i] = dp[i-1];
dp[i] = (dp[i-1]+dp2[i-1])*(k-1);
}
return dp[n-1]+dp2[n-1];
}
