# 276 - Paint Fence

解法一 - DP

不知道為啥這題會是 Easy，個人覺得滿容易卡住的ＸＤ而且最高票的解答讓我覺得很不簡潔，一直看不懂。

還好 這個影片 解釋得還不錯。

而且看完上面的影片，再看 Stefan 大神的解釋就可以看得懂了：

基本想法就是，我們只需要考慮兩種情況：

1. 最後一個 post 跟上一個顏色不同：那就有 dp[i-1]*(k-1) 種可能

2. 最後一個 post 跟上一個顏色相同：那就有 dp[i-2]*(k-1) 種可能（最後兩個共享 k-1 種顏色）

程式碼如下：

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

        vector<int> dp(n+1, 0);
        dp[0] = 0;
        dp[1] = k;   // k ways to paint 1 post
        dp[2] = k*k; // k*k ways to paint 2 posts

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

        return dp[n];
    }
};