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.
Note: n and k are non-negative integers.
涂栅栏条最多两个颜色在一起。艾玛， 闹心， 二刷看答案竟然还要想一会儿！！！尼玛啊
当然这道题得用动态规划， 将1，2栅栏条相同颜色和不同颜色区分开， 分别计算可能性， 返回总和。还要考虑异常条件 没有栅栏和仅有一个栅栏的情况。
空间复杂度O(2n)， 根据规则可以发现只要另个变量O(2) 就可以做到。修改代码。
public int numWays(int n, int k) {
if(n == 0){
return 0;
}
if(n == 1){
return k;
}
int[] dp_same = new int[n];
int[] dp_diff = new int[n];
dp_same[0] = dp_same[1] = k;
dp_diff[0] = k;
dp_diff[1] = k*(k-1);
for(int i = 2; i < n; i++ ){
dp_same[i] = dp_diff[i-1];
dp_diff[i] = (k - 1)*(dp_diff[i-1] + dp_same[i-1]);
}
return dp_diff[n-1] + dp_same[n-1];
}
public int numWays(int n, int k) {
if(n == 0){
return 0;
}
if(n == 1){
return k;
}
int same = k;
int diff = k * (k-1);
for(int i = 2; i < n; i++){
int temp = diff;
diff = (same+diff)*(k-1);
same = temp;
}
return same + diff;
}
