題目
我們有一個柵欄歇终，它有n個柱子，現(xiàn)在要給柱子染色钓简，有k種顏色可以染乌妒。必須保證不存在超過2個相鄰的柱子顏色相同（也就不能有三個顏色連續(xù)的柱子啦）汹想，求有多少種染色方案。（n和k都是非負(fù)整數(shù)）
代碼
public class Solution {
/*
* @param n: non-negative integer, n posts
* @param k: non-negative integer, k colors
* @return: an integer, the total number of ways
*/
/**假設(shè)buff[i]為有i個柱子時的染色方案 可以分為兩種情況
* 1）最后兩根柱子顏色相同撤蚊，2）最后兩根柱子顏色不同
* 對于第一種情況，最后兩根柱子顏色相同侦啸，不能三根柱子顏色連續(xù)相同槽唾，
* 所以最后兩根柱子的顏色選擇有k-1種，所以buff[i-2]k-1匹中；
* 對于第二種情況夏漱，最后兩根柱子顏色不同，那么最后一根柱子的顏色有k-1種選擇方案顶捷，所以buff[i-1]k -1
* 所以綜上挂绰，我們就得出狀態(tài)轉(zhuǎn)移方程為：buff[i] = buff[i-1] (k-1) + buff[i-2] (k-1)；初始條件：buff[1] = k; buff[2] = k*k;
*/
public int numWays(int n, int k) {
if(n==0){
return 0;
}
if(n==1){
return k;
}
if(n==2){
return k*k;
}
int[] buff = new int[n+1];
buff[1] = k;
buff[2] = k*k;
for(int i=3;i<=n;i++){
buff[i] = buff[i-1]*(k-1) + buff[i-2]*(k-1);
}
return buff[n];
}
}
