文章目录
1. 题目2. 解题2.1 DP超时解2.2 DP解
1. 题目
有 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） 链接：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)));
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);
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
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个变量，代码略
长按或扫码关注我的公众号，一起加油、一起学习进步！
