# 276 Paint Fence

訓練dp思考的小題目，總共有n個籬笆，k個顏色，同樣的顏色不能連續重複兩次以上，Given n and k，問總共有幾種塗法。

Concept 先舉個例子觀察一下

If n=3, k=5:
    case 1: post 1 and post 2 has the same color
        5(post1) * 1(post2) * (5-1)(post3) = 20
    case 2: post 1 and post 2 has the diff color
        5(post1) * (5-1)(post2) * 5(post3) = 100
    總共120種可能

分成兩種case，前兩個顏色相同，或前兩個顏色不同。 前兩個顏色相同：最新的post只能在(k-1)個顏色中選（不能再和前面一樣），前一個只有一種可能（和前前一個一樣） 前兩個顏色不同：最新的post可以在k個顏色中選，但前一個只能在(k-1)個顏色中選

Pseudocode

int[] dp = new int[n]
initialize dp[0] dp[1]
for i=2; i<n; i++
    dp[i] = dp[i-2] * (k-1) + dp[i-1] * (k-1)
return dp[n-1]

Code

class Solution {
    public int numWays(int n, int k) {
        if(n == 0)  return 0;
        if(n == 1)   return k;

        int[] dp = new int[n];
        dp[0] = k; dp[1] = k*k;

        for(int i=2; i < n; i++){
            dp[i] = dp[i-2] * (k-1) + dp[i-1] * (k-1);

        }

        return dp[n-1];
    }
}