Leetcode 276.栅栏涂色
Time: 20190904
Type: Easy
考察:动态规划
题目描述
有 k 种颜色的涂料和一个包含 n 个栅栏柱的栅栏,每个栅栏柱可以用其中一种颜色进行上色。
【Leetcode 276.栅栏涂色】你需要给所有栅栏柱上色,并且保证其中相邻的栅栏柱 最多连续两个 颜色相同。然后,返回所有有效涂色的方案数。
注意:
n 和 k 均为非负的整数。
示例:
输入: n = 3,k = 2
输出: 6
解析: 用 c1
表示颜色 1
,c2
表示颜色 2
,所有可能的涂色方案有:
柱 1柱 2柱 3
--------------------
1c1c1c2
2c1c2c1
3c1c2c2
4c2c1c1
5c2c1c2
6c2c2c1
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/paint-fence
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路
定义状态,用
f[i]
表示从左到有走到下标为i
的栅栏时的涂色总数,显然f[0] = k
, f[1] = k * k
,f[2] = k * k * k - k
状态迁移方程:
分成两种情况来思考:
- 当前栅栏颜色和前一个颜色相同,则表示更前一个栅栏颜色和右边两个不同,到更前一个栅栏的涂色方案有
f(i-2)
种,后面两个涂色相同,共k-1
种 - 当前栅栏颜色和前一个不同,则当前栅栏涂色方案有
k-1
种,到前一个栅栏为止,涂色方案有f(i-1)
种
f[i] = (k - 1) * f[i-1] + (k - 1) * f[i-2]
代码
class Solution:
def numWays(self, n: int, k: int) -> int:
if n == 0:
return 0
if n == 1:
return k
if n == 2:
return k * k
f = [0] * n
f[0] = k
f[1] = k * kfor i in range(2, n):
f[i] = f[i-1] * (k - 1) + f[i-2] * (k - 1)return f[-1]
END.
推荐阅读
- 【Leetcode/Python】001-Two|【Leetcode/Python】001-Two Sum
- leetcode|leetcode 92. 反转链表 II
- 二叉树路径节点关键值和等于目标值(LeetCode--112&LeetCode--113)
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器(Swift)
- LeetCode(03)Longest|LeetCode(03)Longest Substring Without Repeating Characters
- Leetcode|Leetcode No.198打家劫舍
- [leetcode数组系列]1两数之和
- 数据结构和算法|LeetCode 的正确使用方式
- leetcode|今天开始记录自己的力扣之路
- LeetCode|LeetCode 876. 链表的中间结点