276._Paint_Fence.md

276. Paint Fence

题目: https://leetcode.com/problems/paint-fence/

难度: Easy

思路：

先解释一下题目意思： fence 栅栏， post 柱子 , no more than two adjacent fence posts have the same color.（一开始看漏，没有看到more than，以为相邻就不能同色）。

本来想画格子找规律，结果走偏了，所以老老实实写递推关系式，貌似是这样的

• n = 0 : 全为0
• n = 1 : 有 k种方式
• n = 2 ：有 k * k 种
• 否则，第n个有两种可能， 跟 n-1 颜色不一样, 跟 n-1 颜色一样， fn = (k-1)fn-1 + (k-1) fn-2

画一下表：对一下递推关系式，正确✅

				n
		0	1	2	3	4
	0	0	0	0	0	0
t	1	0	1	1	0	0
	2	0	2	4	6	10
	3	0	3	9	24	.
	4	0	4	16	60	.

AC 代码

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

            	for i in range(3,n+1):
            		dp[i] = (k-1) * dp [i-1] + (k-1) * dp [i-2]
            	return dp[-1]