Paint Fence

这道题是DP是很容易看出来的，关键在于规律上的问题比较难找出来，自己的思路是每次只考虑隔壁两格颜色一样的情况并将这个情况减掉，这样相当于每次就在之前的一格的基础上乘以k再减去k，这样的结果是不对的，根据答案的思路，应该是当前位置不能和前两格的位置颜色一样，或者不能跟前一格的位置颜色一样即可，如果按照这个逻辑，状态方程如下

dp[i] = (k - 1) * dp[i - 1] + (k - 1) * dp[i - 2]

下面是代码

class Solution(object):
    def numWays(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: int
        """
        res = [k, k * k]
        for i in xrange(2, n):
            res[i % 2] = (k - 1) * res[i % 2] + (k - 1) * res[(i + 1) % 2]
        return res[(n - 1) % 2] if n else 0