276. 栅栏涂色

当只有一个柱子需要涂色时，有k种可涂色方案；

当有两个柱子需要涂色时，有k(k-1)【diff】+k【same】种涂色方案；

当有三个柱子需要涂色时，有（same+diff）*(k-1)【diff】+diff【same】种方案。

 1 class Solution(object):
 2     def numWays(self, n, k):
 3         """
 4         :type n: int
 5         :type k: int
 6         :rtype: int
 7         """
 8         if(n==0):
 9             return 0
10         if(n==1):
11             return k
12         
13         same=k
14         diff=k*(k-1)
15 
16         for i in range(3,n+1):
17             prediff=diff
18             diff=( same+diff )*(k-1)
19             same=prediff    
20                
21         return same+diff