題目連結

題型解說

這是一題難度為簡單的題目

需要設計一個方法，此方法會傳入 柱子的數量(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 隻柱子會有兩種選擇

1. 與前一隻顏色一樣
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 隻柱子一樣會有兩種選擇

1. 與前一隻顏色一樣
2. 與前一隻顏色不一樣

一樣先看第一種(與前一隻顏色一樣)，這邊要結合第二隻柱子的狀況來看，只有第二隻的第二種選擇的數量才是正確的，也就是 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;
    }
}