[leetcode]276-栅栏涂色

马谦马谦马谦 2020年2月9日15:25:25 发表评论

来源:力扣(LeetCode)

链接:https://leetcode-cn.com/problems/paint-fence

著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

一、题目描述

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

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

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

示例

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

二、题解

leetcode标注是简单题目,但是对我这种脑袋不太灵光的人来说,并不太简单,所以多参考了几种解题思路。

2.1 递推

假设前一个栅栏的颜色数量为f(n - 1),再前一个栅栏的颜色数量为f(n - 2

递推的思路:

  1. 如果当前栅栏颜色和前一个栅栏颜色一样,它的选择是k - 1(因为当前栅栏和前一个栅栏颜色一样,所以前一个栅栏颜色和更前一个展览的颜色不能一样,少一种颜色选择),这种情况的颜色数量为f(n - 2) * (k - 1)
  2. 如果当前栅栏颜色和前一个栅栏颜色不一样,那么当前栅栏的颜色选择就只有k - 1种,总的颜色数量为f(n - 1) * (k - 1)

总结出来的递推公式:f(n) = f(n - 1) * (k - 1) + f(n - 2) * (k - 1)

代码:

2.2 动态规划

以前面两个栅栏的颜色来确定当前栅栏的颜色:

  1. 如果前两个栅栏的颜色相同,那么当前栅栏的颜色有k - 1种。
  2. 如果前两个栅栏的颜色不同,那么当前栅栏的颜色有k种。

分别以dp1和dp2保存颜色相同和不同的种数,可以总结出来的状态转移方程:

  • dp1 = prev_dp1
  • dp2 = (k - 1) * (dp1 + dp2)

dp1是相同的颜色数量,它和上一个栅栏颜色相同,所以就等于上一个栅栏颜色数量。dp2是不同的颜色数量,它等于上一个栅栏颜色总量的和乘以k - 1

代码:

[leetcode]276-栅栏涂色

本文共执行66次查询,耗时0.916秒!
历史上的今天
二月
9
马谦马谦马谦

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: