|
1、题目描述（Lintcode）
我们有一个栅栏，它有n个柱子，现在要给柱子染色，有k种颜色可以染。必须保证不存在超过2个相邻的柱子颜色相同，求有多少种染色方案。 题目链接：栅栏染色
2、题目解析
首先设置一个dp数组用于记录给第i个柱子染色的时候一共有多少种染色方案，即dp[i]。我们接着寻找规律，我们发现当染三个柱子的时候，如果第一和第二个柱子的颜色不一样，那么第三个柱子任意染什么颜色都可以，不受第一个柱子颜色的影响。但是如果第一个和第二个柱子的颜色一样，那么第三个柱子要受到前两个柱子颜色的影响，因为题目规定，不能存在超过两个相邻的柱子颜色相同。 接下我们可以分两种情况：
假如第一个柱子和第二个柱子的颜色不一样，那么
d
p
[
0
]
=
k
，
d
p
[
1
]
=
k
×
(
k
−
1
)
dp[0] = k，dp[1] = k \times (k-1)
dp[0]=k，dp[1]=k×(k−1)。所以
d
p
[
2
]
=
k
×
(
k
−
1
)
×
k
dp[2]=k \times (k-1) \times k
dp[2]=k×(k−1)×k假如第一个柱子和第二个柱子的颜色一样，那么
d
p
[
0
]
=
k
，
d
p
[
1
]
=
k
dp[0] = k，dp[1] = k
dp[0]=k，dp[1]=k。所以
d
p
[
2
]
=
k
×
(
k
−
1
)
dp[2]=k \times (k-1)
dp[2]=k×(k−1)
以此类推，dp[1]，dp[2]，dp[3]也符合以上的规律。综上，我们归纳出dp[i-2]，dp[i-1]，dp[i]分别对应第i-2个柱子，第i-1个柱子，第i个柱子。将以上两种情况合并，我们得到
d
p
[
0
]
=
k
dp[0]=k
dp[0]=k（因为只有k个染色方案），
d
p
[
1
]
=
k
×
(
k
−
1
)
+
k
=
k
2
dp[1]=k \times (k-1) + k=k^2
dp[1]=k×(k−1)+k=k2，
d
p
[
2
]
=
k
×
(
k
−
1
)
×
k
+
k
×
(
k
−
1
)
=
(
k
−
1
)
×
k
×
(
k
+
1
)
dp[2]=k \times (k-1) \times k+k \times (k-1)=(k-1) \times k \times (k+1)
dp[2]=k×(k−1)×k+k×(k−1)=(k−1)×k×(k+1)。得到
d
p
[
0
]
×
(
k
−
1
)
+
d
p
[
1
]
×
(
k
−
1
)
=
d
p
[
2
]
dp[0] \times (k-1)+dp[1] \times (k-1)=dp[2]
dp[0]×(k−1)+dp[1]×(k−1)=dp[2]，归纳为
d
p
[
i
−
2
]
×
(
k
−
1
)
+
d
p
[
i
−
1
]
×
(
k
−
1
)
=
d
p
[
i
]
dp[i-2] \times (k-1)+dp[i-1] \times (k-1)=dp[i]
dp[i−2]×(k−1)+dp[i−1]×(k−1)=dp[i]
3、代码
public class Solution {
/**
* @param n: non-negative integer, n posts
* @param k: non-negative integer, k colors
* @return: an integer, the total number of ways
*/
public int numWays(int n, int k) {
// write your code here
int[] dp = new int[n];
//一直向前探索
dp[0] = k;
int count = 0;
if(n == 1){
count = dp[0];
}else if(n == 2){
dp[1] = k * k;
count = dp[1];
}else{
dp[1] = k * k;
for(int i = 2;i |