有 k 種顏色的涂料和一個包含 n 個柵欄柱的柵欄，每個柵欄柱可以用其中一種顏色進行上色。

你需要給所有柵欄柱上色，并且保證其中相鄰的柵欄柱 最多連續兩個?顏色相同。然后，返回所有有效涂色的方案數。

注意:
n 和?k 均為非負的整數。

示例:

輸入: n = 3，k = 2
輸出: 6
解析: 用 c1 表示顏色 1，c2 表示顏色 2，所有可能的涂色方案有:

?? ? ? ? ? ?柱 1 ? ?柱 2 ? 柱 3 ? ??
?----- ? ? ?----- ?----- ?----- ? ? ??
? ?1 ? ? ? ? c1 ? ? c1 ? ? c2?
?? 2 ? ? ? ? c1 ? ? c2 ? ? c1?
?? 3 ? ? ? ? c1 ? ? c2 ? ? c2?
?? 4 ? ? ? ? c2 ? ? c1 ? ? c1??
? ?5 ? ? ? ? c2 ? ? c1 ? ? c2
?? 6 ? ? ? ? c2 ? ? c2 ? ? c1

思路：動態規劃。

n=1,k鐘

n=2,k*k種。

n>2:

n可以和n-1位置顏色相同，這時這兩個位置可選項有k-1種顏色可用，再乘n-2位置方案總數。

n可以和n-1位置顏色不同，這時這個位置有k-1種顏色可用，再乘n-1位置的方案總數。

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

?