[LeetCode] #276 Paint Fence 解題
題型解說
這是一題難度為簡單的題目
需要設計一個方法，此方法會傳入 柱子的數量(n) 及 顏色的數量(k)
且 n 與 k 為正整數
試問可以組合出幾種顏色的組合，且相同顏色不可以連續兩隻以上
範例: n = 3，k = 2 可以組合出六種結果
顏色我們就用 R 跟 B 代替
- 第一種組合 R R B
- 第二種組合 R B R
- 第三種組合 R B B
- 第四種組合 B B R
- 第五種組合 B R B
- 第六種組合 B R R
我們來看一下錯誤的組合
R R R
因為限制為相同顏色只能連續兩隻，所以一但三隻都漆上紅色，就違反規則
解題思路
這一題雖然列為簡單，但實際上還是有一定的難度
主要是想辦法發現規律，沒接觸過的人大概得要想半天吧
那我們就從柱子的數量來說一下規律，假設顏色有三種 R G B
柱子數量為 1
如果柱子數量為 1，那答案就是顏色的數量 k，應該沒有什麼歧義
- 第一種組合 R
- 第二種組合 G
- 第三種組合 B
柱子數量為 2
如果柱子數量為 2，第 2 隻柱子會有兩種選擇
- 與前一隻顏色一樣
- 與前一隻顏色不一樣
先來看第一種(與前一隻顏色一樣)，比較單純，組合一樣是 k(3) 種
- 第一種組合 R R
- 第二種組合 G G
- 第三種組合 B B
再來看第二種(與前一隻顏色不一樣)，組合是 (k(3) - 1) * 上一隻柱子的數量(3) = 6種
- 第一種組合 R G
- 第二種組合 R B
- 第三種組合 G R
- 第四種組合 G B
- 第五種組合 B R
- 第六種組合 B G
柱子數量為 2 的答案就是兩種選擇的數量的加總 6 + 3 = 9
柱子數量為 3
如果柱子數量為 3，第 3 隻柱子一樣會有兩種選擇
- 與前一隻顏色一樣
- 與前一隻顏色不一樣
一樣先看第一種(與前一隻顏色一樣)，這邊要結合第二隻柱子的狀況來看，只有第二隻的第二種選擇的數量才是正確的，也就是 6 種
- 第一種組合 R G G
- 第二種組合 R B B
- 第三種組合 G R R
- 第四種組合 G B B
- 第五種組合 B R R
- 第六種組合 B G G
那為什麼不算第二隻的第一種選擇的數量呢？因為第二隻的第一種選擇已經與第一隻柱子的顏色相同了，如果第三隻還算進去的話就會變成違反規則
- 第一種組合 R R R
- 第二種組合 G G G
- 第三種組合 B B B
上面哪一種組合都是違反規則的
再來看第二種(與前一隻顏色不一樣)，組合是 (k(3) - 1) * 上一隻柱子的數量(9) = 18種
- 第一種組合 R R G
- 第二種組合 R R B
- 第三種組合 G G R
- 第四種組合 G G B
- 第五種組合 B B R
- 第六種組合 B B G
- 第七種組合 R G R
- 第八種組合 R G B
- 第九種組合 R B R
- 第十種組合 R B G
- 第十一種組合 G R B
- 第十二種組合 G R G
- 第十三種組合 G B R
- 第十四種組合 G B G
- 第十五種組合 B R G
- 第十六種組合 B R B
- 第十七種組合 B G R
- 第十八種組合 B G B
柱子數量為 3 的答案就是兩種選擇的數量的加總 6 + 18 = 24
柱子數量為 4 的情況就自己列列看吧，如果算出來的數量是 66 的話就對了
規律
由上面的範例來看，可以發現一個規律
第 n 隻柱子的組合數量為: 第 n - 1 隻柱子的第二種選擇(與前一隻顏色不一樣)的數量 + (k - 1) * 第 n - 1 隻柱子的總數
那第 n - 1 隻柱子的組合數量為: 第 n - 2 隻柱子的第二種選擇(與前一隻顏色不一樣)的數量 + (k - 1) * 第 n - 2 隻柱子的總數
以此類推，這樣就可以用一個迴圈來算出解答了
程式碼
Java
class Solution {
public int numWays(int n, int k) {
if (n == 0 || k == 0 || (k == 1 && n > 2)) {
return 0;
}
if (n == 1) {
return k;
}
int same = 0; // 與上一隻柱子顏色相同
int diff = k; // 與上一隻柱子顏色不同
int total = k; // 總數
for (int i = 2; i <= n; i++) {
same = diff;
diff = (k -1) * total;
total = same + diff;
}
return total;
}
}