Paint Fence

这个居然是easy题…这个dp真的有点难难度. 首先观察第i个可涂的颜色, 可以涂和i-1一样, 也可以不一样, 一样是k-1个涂法, 不一样呢? 不一样的话, 因为不能三个连续一样, 那么如果和前边一个不一样, 就要保证前边两个是一样的, 换句话说, 就是和i-2的不一样, 那么也是k-1个….这个很难想到..