Paint fence

這題要想出當前的柱子與前面的柱子的著色關係，

因為不能有超過連續兩個重複，所以我們必須要看當前的(cur) 和前一個 (n-1) 和前前一個(n-2)的關係

如果我們以 f(n) 表示 n 個柱子可能的著色數，

那 f(cur) 有兩種情況，

• 一種是與前面一樣顏色，那我們應該看 f(n-2) 有多少，因為不能有超過連續兩個重複，所以這種情況是 (k-1)*f(n-2) => 因為當前前一個是某種顏色後，前一個和當前只能是 (k-1) 種
• 另一種情況是 cur 和前一個不同，既然要不同，表示剩下 (k-1) 種顏色，所以數量是 (k-1)*f(n-1)

=> f(cur) = (k-1)*f(n-2) + (k-1)*f(n-1)

就是這樣而已!!!!!!!

而 base condition = f[0] = 0, f[1] = k, f[2] = k*k

public int numWays(int n, int k) {
    int f[] = new int[] {0, k, k*k, 0};
    if (n <= 2)
        return f[n];

    for (int i=3; i<=n; i++) {
        f[3] = (k-1)*f[2] + (k-1)*f[1]; //diff + same
        f[1] = f[2];
        f[2] = f[3];
    }
    return f[3];
}