来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/paint-fence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
一、题目描述
有 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
二、题解
leetcode标注是简单题目，但是对我这种脑袋不太灵光的人来说，并不太简单，所以多参考了几种解题思路。
2.1 递推
假设前一个栅栏的颜色数量为f(n - 1)，再前一个栅栏的颜色数量为f(n - 2。
递推的思路：
- 如果当前栅栏颜色和前一个栅栏颜色一样，它的选择是
k - 1（因为当前栅栏和前一个栅栏颜色一样，所以前一个栅栏颜色和更前一个展览的颜色不能一样，少一种颜色选择），这种情况的颜色数量为f(n - 2) * (k - 1)。 - 如果当前栅栏颜色和前一个栅栏颜色不一样，那么当前栅栏的颜色选择就只有
k - 1种，总的颜色数量为f(n - 1) * (k - 1)。
总结出来的递推公式：f(n) = f(n - 1) * (k - 1) + f(n - 2) * (k - 1)。
代码：
class Solution {
public:
int numWays(int n, int k) {
int prev, pprev, rs, i;
if (n <= 0 || k <= 0)
return 0;
if (n == 1)
return k;
pprev = k;
prev = k * k;
rs = prev;
for (i = 2; i < n; i++) {
rs = pprev * (k - 1) + prev * (k - 1);
pprev = prev;
prev = rs;
}
return rs;
}
};2.2 动态规划
以前面两个栅栏的颜色来确定当前栅栏的颜色：
- 如果前两个栅栏的颜色相同，那么当前栅栏的颜色有k - 1种。
- 如果前两个栅栏的颜色不同，那么当前栅栏的颜色有k种。
分别以dp1和dp2保存颜色相同和不同的种数，可以总结出来的状态转移方程：
- dp1 = prev_dp1
- dp2 = (k - 1) * (dp1 + dp2)
dp1是相同的颜色数量，它和上一个栅栏颜色相同，所以就等于上一个栅栏颜色数量。dp2是不同的颜色数量，它等于上一个栅栏颜色总量的和乘以k - 1。
代码：
class Solution {
public:
int numWays(int n, int k) {
int dp1, dp2, rs, i;
if (n <= 0 || k <= 0)
return 0;
if (n == 1)
return k;
dp1 = k;
dp2 = k * (k - 1);
for (i = 2; i < n; i++) {
rs = (dp1 + dp2) * (k - 1);
dp1 = dp2;
dp2 = rs;
}
return dp1 + dp2;
}
};
