276 - Paint Fence

解法一 - DP

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

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

而且看完上面的影片,再看 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];
    }
};

results matching ""

    No results matching ""