514.栅栏染色

514. 栅栏染色

中文English

我们有一个栅栏，它有n个柱子，现在要给柱子染色，有k种颜色可以染。
必须保证不存在超过2个相邻的柱子颜色相同，求有多少种染色方案。

样例

例 1:

输入: n=3, k=2  
输出: 6
Explanation:
          post 1,   post 2, post 3
    way1    0         0       1 
    way2    0         1       0
    way3    0         1       1
    way4    1         0       0
    way5    1         0       1
    way6    1         1       0

例 2:

输入: n=2, k=2  
输出: 4
Explanation:
          post 1,   post 2
    way1    0         0       
    way2    0         1            
    way3    1         0          
    way4    1         1       

注意事项

n和k都是非负整数

输入测试数据 (每行一个参数)如何理解测试数据？

class Solution:
    """
    @param n: non-negative integer, n posts
    @param k: non-negative integer, k colors
    @return: an integer, the total number of ways
    """
    def numWays(self, n, k):
        # write your code here
        dic = [0,k,k**2]
        print(dic)
        if n in [0,1,2]:
            return dic[n]
        print(dic)
        ##否则  
        for n in range(2,n):    
            ##从第三个柱子开始，之后的柱子分为和上一个柱子颜色相同和不同的部分
            ##如果是相同的部分的话,那么必须保证当前柱子的当前柱子的前两个是不同的颜色，才可以。>>>>>>dic[-2]*(k-1)  特别注意:当前柱子前两个相同的方案有dic[-2]*k种
            ##如果是不同的部分的话，很容易理解，只需要*(k-1)即可>>上一个柱子的方案*(k-1)即为当前柱子不同的方案数量
            res =dic[-2]*(k-1)+dic[-1]*(k-1)
            dic.append(res)
        return dic[-1]

大致解释:(可以基本判断柱子为0,1,2的时候染色的方案总数,柱子数量大于2之后的可以依次推导出来)

1.当柱子数量为0,1,2的时候，k随便，染色的方案数量分别为0,k,k**2(注意，相邻柱子是最多只能两个颜色相同,所以不是k*(k-1))

2.当柱子数量大于2的时候，此时分别和上一个柱子颜色相同和不同两种方向

(1).如果是和上一个柱子颜色相同，此时必须保证当前柱子的前两个柱子的颜色不同,才能和上一个柱子颜色相同。前两个柱子颜色不同的方案数量是:dic[-2]*(k-1)。注意:dic[-2]为前两个柱子染色方案总数，前两个柱子染色颜色相同的数量为dic[-2]*1

(2).如果是和上一个柱子颜色不同，此时很好理解，这就是dic[-1]*(k-1)就是结果了

3.柱子大于2的染色方案数量依次类推就好了,dic[-1]*(k-1)+dic[-2]*(k-1),即for n in range(2,n):dic.append(dic[-1]*(k-1)+dic[-2]*(k-1))。

 优化代码:

class Solution:
    """
    @param n: non-negative integer, n posts
    @param k: non-negative integer, k colors
    @return: an integer, the total number of ways
    """
    '''
    1.如果是0,1,2个柱子的话，染色方案可以直接得到
    2.如果是大于2个柱子的话，那么染色方案可以计算得到
    (1).如果要和上一个柱子染色相同的话，那么前两个柱子必须不同颜色，dic[-2]*(k-1)*1
    (2).如果要和上一个柱子染色不同的话，那么前两个柱子颜色相同和不相同均可。dic[-1]*(k-1)
    3.多少个柱子就循环多少次即可(从2开始)
    '''
    def numWays(self,n,k):
        ##如果是0,1,2个柱子的话，那么染色方案是固定的
        dic = [0,k,k**2]

        ##如果是大于2个柱子的话，那么根据规律来计算
        for i in range(2,n):
            dic.append(dic[-2]*(k-1)*1+dic[-1]*(k-1))
        return dic[n]