276. Paint Fence (Easy)

There is a fence with n posts, each post can be painted with one of the k colors.

You have to paint all the posts such that no more than two adjacent fence posts have the same color.

Return the total number of ways you can paint the fence.

Note:

n and k are non-negative integers.

Solution: DP

这道题是之前那道Flip Game的拓展，让我们判断先手的玩家是否能赢，那么我们可以穷举所有的情况，用回溯法来解题，我们的思路跟上面那题类似，也是从第二个字母开始遍历整个字符串，如果当前字母和之前那个字母都是+，那么我们递归调用将这两个位置变为--的字符串，如果返回false，说明当前玩家可以赢，结束循环返回false，参见代码如下：

class Solution {
public:
    int numWays(int n, int k) {
        if (n == 0) return 0;
        int same = 0, diff = k; // 1 post k choice
        for (int i = 2; i <= n; ++i) {
            int t = diff;
            diff = (same+diff)*(k-1);
            same = t;
        }
        return same + diff;
    }
};