Lintcode514 Paint Fence solution

【题目描述】

There is a fence with n posts, each post can be painted with one of the k colors.

You have to paint all the posts such that no more than two adjacent fence posts have the same color.

Return the total number of ways you can paint the fence.

 Notice

n and k are non-negative integers.

我们有一个栅栏，它有n个柱子，现在要给柱子染色，有k种颜色可以染。

必须保证不存在超过2个相邻的柱子颜色相同，求有多少种染色方案。

 注意事项

n和k都是非负整数

【题目链接】

www.lintcode.com/en/problem/paint-fence/

【题目解析】

DP[i]表示第i个柱子最多的选择数。在计算DP[i]时，考虑两种情况：

和第i－1柱子不同颜色，则可以有(k-1) * DP[i-1]个选择

和第i－1柱子相同颜色，此时要求i－1柱子和i－2柱子不同颜色（即第一种情况，只是换成了第i－1根柱子和第i－2根柱子不同颜色），所以有(k-1) * DP[i-2]个选择

因此总选择数为(k-1) * (DP[i-1] + DP[i-2])

因为只和前两个柱子相关，所以可以用滚动数组来优化空间。

【参考答案】

www.jiuzhang.com/solutions/paint-fence/