276 Paint Fence
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]
