[leetcode]276-栅栏涂色

来源：力扣 （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 。

代码：