跳转至

LeetCode: 276. 栅栏涂色

1、题目描述

有 k 种颜色的涂料和一个包含 n 个栅栏柱的栅栏,每个栅栏柱可以用其中一种颜色进行上色。

你需要给所有栅栏柱上色,并且保证其中相邻的栅栏柱 最多连续两个 颜色相同。然后,返回所有有效涂色的方案数。

注意: n 和 k 均为非负的整数。

示例:

输入: n = 3,k = 2
输出: 6
解析: 用 c1 表示颜色 1,c2 表示颜色 2,所有可能的涂色方案有:

            柱 1    柱 2   柱 3     
 -----      -----  -----  -----       
   1         c1     c1     c2 
   2         c1     c2     c1 
   3         c1     c2     c2 
   4         c2     c1     c1  
   5         c2     c1     c2
   6         c2     c2     c1

2、解题思路

记录两个值:

  • 当前柱子和前一个柱子颜色相同的方案数量
  • 当前柱子和前一个柱子颜色不同的方案数量

为何这样就能得到结果呢?

当前柱子的解决方案数量一共有两种,当前柱子染色方案要么和前一个相同,要么不相同

  • 染色相同的话,那么当前柱子就不能和前前一个相同,因此,假如知道了前一个柱子与前前柱子不同的方案数量,这样的话,当前的相同的染色数量就等于这个
  • 染色不同的时候,就是前面柱子每一种方案,除去本身的颜色以外的其他颜色
颜色:2

柱子1
    相同颜色为0
    不同颜色为2
    一共两个染色方案

柱子2
  相同颜色为2
  不同颜色方案:2*1 , 为什么是2*1呢?因为前面柱子一共2中染色,如果想要不同,就是去掉前面柱子的颜色,所以就是2*1
  所有的染色方案就是4
class Solution:
    def numWays(self, n: int, k: int) -> int:
        if not n or not k:
            return 0
        same = 0
        diff = k
        res = same + diff

        for i in range(1, n):
            same = diff
            diff = res * (k-1)
            res = same+diff

        return res