LeetCode 破關之路- 276 Paint Fence

閒來無事，來寫一下昨天複習的一個題目。

這題是Leetcode的上鎖題，其題目意思是，假設有一排欄桿，並給你K種顏色的油漆，假設最多只有連續兩個欄桿能漆同樣的顏色，總共有幾種漆法。

這題是一個DP的題目，這邊先舉幾個例子，假設有紅(R)、綠(G)、藍(B)三種顏色，用k來代表顏色數。則

欄桿1  欄桿2  欄桿3
R      R     R    (不合法)
R      R     B    (合法)
R      R     G    (合法)
R      G     B    (合法)
B      R     R    (不合法)

所以你可以發現兩種情況
* 情況1: 目前的欄桿和前一根欄桿顏色一樣 (same)
* 情況2:目前的欄桿和前一根欄桿顏色不一樣 (different)
而情況1和情況2加總機是總共的漆法。

我們先看情況2比較簡單，此種情況，我們就看前一次總共漆了多少種顏色(preTotal)，而目前的欄桿和前一個不一樣，所以就是different = PreTotal * (k-1)。

麻煩的是情況1，因為有一個限制，就是只能連續兩個欄桿顏色一樣。我們可以用下面的表格想一下:

情況2就是PreTotal * (k-1)，所以欄桿2為3*(3–1)，欄桿3為9*(3–1)。而情況一的條件是不能連續的欄桿一樣，所以表示我們要排除前一支的欄桿漆的顏色和前前支相同的情況，換句話說，如果我們目前的欄桿要漆的和前一支一樣，只能用前一支和前前支不同的顏色(這邊有點難想)。換成上面的變數，也就是目前我這支欄桿可以漆的顏色，和前一支欄桿不能和前前支漆成的顏色相同。所以其DP公式為:

same = different
different = preTotal * (k-1)
ans = different+ same

其完整的程式碼如下

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;
            
        int total = k;
        int diff = k;
        for (int i = 2; i <= n; i++) {
            int same = diff;
            diff = total * (k-1);
            total = diff + same;
        }
        
        return total;
    }
}