題目
我們有一個柵欄鸭廷，它有n個柱子，現(xiàn)在要給柱子染色熔吗，有k種顏色可以染辆床。
必須保證任意兩個相鄰的柱子顏色不同，求有多少種染色方案桅狠。
** 原題應(yīng)該表述有誤讼载，原文是“必須保證任意兩個相鄰的柱子顏色不同，應(yīng)該表述為“不能有連續(xù)三個柱子顏色相同”中跌。**
分析
這也是典型的動態(tài)規(guī)劃問題咨堤，我們一樣從最后的情況開始討論。
假設(shè)buff[i]為有i個柱子時的染色方案漩符∫淮可以分為兩種情況：
- 最后兩根柱子顏色相同
- 最后兩根柱子顏色不同
對于第一種情況，最后兩根柱子顏色相同嗜暴，不能三根柱子顏色連續(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 class Solution {
/**
* @param n non-negative integer, n posts
* @param k non-negative integer, k colors
* @return an integer, the total number of ways
*/
public int numWays(int n, int k) {
// Write your code here
if (n == 0)
return 0;
if (n == 1)
return k;
if (n == 2)
return k*k;
int pre = k;
int now = k*k;
for (int i = 3; i <= n; i++)
{
int tmp = now;
now = (pre+now) * (k-1);
pre = tmp;
}
return now;
}
}
