Paint Fence

Problem: Paint Fence

Suppose we've already painted several posts. If we are going to paint a new post. We can paint it as the color of previous one, or different from that. For the first method, we need to paint last two posts different from the last third post. For the second method, we need to paint the new one different from the previous one.

Code in Python:

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