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

递推的思路：

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)。

代码：

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 动态规划

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

1. 如果前两个栅栏的颜色相同，那么当前栅栏的颜色有k - 1种。
2. 如果前两个栅栏的颜色不同，那么当前栅栏的颜色有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;
    }
};