276. Paint Fence

做题历程：

1. 本题应该做了不止1次了，本次独立解决，大概耗时16分钟

本题是用dynamic programming，整体难度并不高。需要注意一点的是：要分别考虑最后两个是相同或者不同这两种情况。。

即设定两个vector<int>，求分别的递推公式即可，代码如下：

class Solution {
public:
    int numWays(int n, int k) {
        if (n == 0 || k == 0) {
            return 0; 
        }
        if (n == 1) {
            return k;
        }
        vector<int> dp1(n, 0);      // last two posts are in same color
        vector<int> dp2(n, 0);      // last two posts are not in the same color
        dp1[0] = 0;
        dp2[0] = k;
        for (int i = 1; i < n; ++i) {
            dp1[i] = dp2[i-1] * 1;
            dp2[i] = dp1[i-1] * (k - 1) + dp2[i-1] * (k - 1);
        }

        return dp1[n-1] + dp2[n-1];
    }
};