276. 栅栏涂色

Difficulty
Medium
Tags
动态规划
URL
https://leetcode.cn/problems/paint-fence/
Star
有 k 种颜色的涂料和一个包含 n 个栅栏柱的栅栏，请你按下述规则为栅栏设计涂色方案：
每个栅栏柱可以用其中 一种 颜色进行上色。 相邻的栅栏柱 最多连续两个 颜色相同。 给你两个整数 k 和 n ，返回所有有效的涂色 方案数 。
示例 1：
notion imagenotion image
输入：n = 3, k = 2
输出：6
解释：所有的可能涂色方案如上图所示。注意，全涂红或者全涂绿的方案属于无效方案，因为相邻的栅栏柱 最多连续两个 颜色相同。
示例 2：
输入：n = 1, k = 1
输出：1
示例 3：
输入：n = 7, k = 2
输出：42
提示：
  • 1 <= n <= 50
  • 1 <= k <= 105
  • 题目数据保证：对于输入的 n 和 k ，其答案在范围 [0, 231 - 1] 内
法1 动态规划-第一类基本型
思路
每个房子有两种状态：
  • 和前一所房子颜色相同
  • 和前一所房子颜色不同
notion imagenotion image
  • 颜色相同的话，方案数是不会变的，即 dp[i][1] = dp[i-1][1]
  • 颜色不一样，那么可以在前一所房子的基础上进行累加方案：dp[i][0] = dp[i-1][0] * (k-1) + dp[i-1][1] * (k-1)
注：为什么这里需要累加 dp[i-1][0]呢？即为什么需要红线呢？dp[i-1][0]表示 第 i-1 所房子颜色和 第i-2所房子颜色相同，那么第 i所当然可以可 i-2 所颜色一样，所以这里表面上看是 累计了 dp[i-1][0], 其实是累计的dp[i-2]的方案数。
题解
class Solution:
    def numWays(self, n: int, k: int) -> int:
        dp = [[0] * 2 for _ in range(n)]
        dp[0][0], dp[0][1] = 0, k
        
        for i in range(1, n):
            dp[i][0] = dp[i-1][1]
            dp[i][1] = dp[i-1][0] * (k-1) + dp[i-1][1] * (k-1)

        return sum(dp[-1])

法 2 参考 隔一天买股票的写法

思路
notion imagenotion image
题解
class Solution:
    def numWays(self, n: int, k: int) -> int:
        if n <= 2:
            return k ** n
            
        dp = [0 for _ in range(n)]
        dp[0], dp[1] = k, k*k
        
        for i in range(2, n):
            dp[i] = dp[i-1] * (k-1) + dp[i-2] * (k-1)

        return dp[-1]