题目大意：
粉刷栅栏
一个栅栏上有n个柱子，每个柱子可以从k个颜色中选择一种进行粉刷。
粉刷所有柱子，并且最多只允许2棵相邻柱子颜色相同。
求总共的粉刷方案数。
注意：n和k都是非负整数。
示例：
输入: n = 3, k = 2 输出: 6 解释: 颜色1为c1，颜色2为c2，所有的粉刷方案如下: post1 post2 post3 ----- ----- ----- ----- 1 c1 c1 c2 2 c1 c2 c1 3 c1 c2 c2 4 c2 c1 c1 5 c2 c1 c2 6 c2 c2 c1
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=276
解题思路分析：
我们可以按照从左至右的顺序粉刷柱子，当前柱子可以选择的颜色种类取决于，相邻之前柱子连续相同颜色的个数。如果之前相同个数等于2，说明这个颜色当前不能使用，因此可选的颜色种类为k-1。在这k-1种颜色中任选一种都不会和之前相邻的颜色冲重复，因此，此时连续相同颜色变为1，递归至下一层继续。如果之前的连续相同颜色数小于2，那么我们不仅可以使用其他的k-1种颜色，同时还可以使用相邻之前柱子的颜色，此时，可选择的颜色种类为1，连续相同颜色个数加一。
实现代码：
int[][] memo; // 记忆数组
public int numWays(int n, int k) {
// 例外情况返回0
if(n==0 || k==0 || k==1 && n>2) return 0;
// 初始化记忆数组
memo=new int[n][3];
// 递归求解
return help(n,k,0,0);
}
int help(int n, int k, int index, int sameCount){
// 如果越界，返回1
if(index==n) return 1;
// 如果记忆数组中存在当前解，返回记忆数组中的值
if(memo[index][sameCount]>0) return memo[index][sameCount];
// 返回值
int count=0;
// 如果连续相同颜色数小于等于1，
if(sameCount<=1){
// 选择与之前相同的颜色，连续相同颜色数加一
count+= help(n, k, index+1, sameCount+1);
}
// 选择与之前不同的颜色，有k-1中选法
// 此时连续相同颜色为1
count+= (k-1)*help(n, k, index+1, 1);
// 将结果保存至记忆数组
memo[index][sameCount]=count;
return count;
}本题解法执行时间为0ms。
Runtime: 0 ms, faster than 100.00% of Java online submissions for Paint Fence.
Memory Usage: 32.8 MB, less than 22.22% of Java online submissions for Paint Fence.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-276-paint-fence-解题思路分析/