1. 题目
有 k 种颜色的涂料和一个包含 n 个栅栏柱的栅栏，每个栅栏柱可以用其中一种颜色进行上色。
你需要给所有栅栏柱上色，并且保证其中相邻的栅栏柱 最多连续两个 颜色相同。然后，返回所有有效涂色的方案数。
注意: n 和 k 均为非负的整数。
代码语言：javascript复制示例:
输入: 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） 链接：https://leetcode-cn.com/problems/paint-fence 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 解题
2.1 DP超时解
- 超时例子， 64 / 79 个通过测试用例
2 n
46340 k，时间复杂度O(nk^2)class Solution {
public:
int numWays(int n, int k) {
if(n==0 || k==0)
return 0;
int conti = 2;//最多连续的次数
vector<vector<vector<int>>> dp(n,vector<vector<int>>(k,vector<int>(conti 1,0)));
//dp[i][c][conti]表示遍历完i栅栏，其颜色为c，c颜色连续了conti次的方案数
int i, c, nc, ct;
for(c = 0; c < k; c)
dp[0][c][1] = 1;
for(i = 1; i < n; i)
{
for(c = 0; c < k; c)
{
for(ct = 1; ct <= conti; ct)
for(nc = 0; nc < k; nc)
{
if(c == nc && ct 1 <= conti)
dp[i][nc][ct 1] = dp[i-1][c][ct];
else if(c != nc)
dp[i][nc][1] = dp[i-1][c][ct];
}
}
}
int sum = 0;
for(c = 0; c < k; c)
for(ct = 1; ct <= conti; ct)
sum = dp[n-1][c][ct];
return sum;
}
};2.2 DP解
- 前两个颜色一样，dp[i-2] 的方案数，
dp[i-2]*1*(k-1)，i 跟他们必须不一样（k-1种选择） - 前两个颜色不一样，i-2 占了一种颜色， i-1 占了一种颜色，i 还能选择 k-1 种颜色（可以跟 i-2 一样），方案数为
dp[i-1]*(k-1)
class Solution {
public:
int numWays(int n, int k) {
if(n==0 || k==0)
return 0;
vector<int> dp(n,0);
//dp[i]表示遍历完i栅栏的方案数
if(n>=1)
dp[0] = k;
if(n>=2)
dp[1] = k*k;
for(int i = 2; i < n; i)
{
dp[i] = dp[i-1]*(k-1) dp[i-2]*(k-1);
}
return dp[n-1];
}
};0 ms 6.2 MB
代码语言：javascript复制class Solution: # py3
def numWays(self, n: int, k: int) -> int:
if n==0 or k==0:
return 0
dp = [0]*n
if n >= 1:
dp[0] = k
if n >= 2:
dp[1] = k**2
for i in range(2, n):
dp[i] = (dp[i-1] dp[i-2])*(k-1)
return dp[n-1]36 ms 13.6 MB
- 状态可以进一步压缩成3个变量，代码略
